2차원 배열에서의 조합

2차원 배열에서 조합

2차원 배열의 조합은 1차원과 달라서 for문에 예전에 뽑았던 x,y 좌표의 +1씩만큼 돌기 시작하면 대각선 조합만 고르게 된다. 따라서 x 또는 y 좌표 값을 동시가 아닌 하나씩 변경하면서 순차적으로 탐색해야 한다. 이를 위해서는 좌표를 1차원 인덱스로 변환하거나 행-열 기준으로 다음 좌표를 가야한다.

좌표를 1차원 인덱스로 변환

void combination2D(int depth, int start) {
    if (depth == K) {
        // 조합 생성 완료
        return;
    }

    for (int i = start; i < N * M; i++) {
        int x = i / M;  // 행 계산
        int y = i % M;  // 열 계산

        pick[depth][0] = x; // x 좌표 저장
        pick[depth][1] = y; // y 좌표 저장

        combination2D(depth + 1, i + 1);
    }
}

조합에서는 중복 방문 확인이 필요없지만...

bfs/dfs 그래프 순회, 순열 등에는 중복 방문 체크가 무한 루프를 방지하기 위해 필요한 경우가 대부분.

bfs 방문처리

중복 방문하지 않으려면 큐에 넣기 전에 해야하는 것 같다...
bfs/dfs 방문처리는 조금 더 공부하기...