[코딩테스트] 2차원 격자 DFS, BFS 문제 팁 (C++)

3개월 정도 코딩테스트를 준비하면서 얻은 팁을 공유하고자 한다. 2차원 격자(배열)에 대해 DFS, BFS로 문제를 풀 때 사용할 수 있는 팁을 써보겠다.

먼저 격자의 좌표를 나타낼 때에는 변수명으로 x,y 혹은 y,x 보다 r, c를 사용하는 것이 낫다. 개인차가 있을 것 같지만 y, x를 사용하면 직관적으로 행,열을 구분하는게 뇌에서 한 번 걸리는 느낌이 들었다. 하지만 row(행), column(열)의 앞문자인 r, c를 사용하니 한 번도 헷갈린 적이 없다. 특히 선형대수학을 이수했다면 r, c 표현이 익숙할 것이다.

//  	   c == 0 c == 1 c == 2 c == 3 ...
// r == 0
// r == 1
// r == 2
// r == 3
//  ...
#include <iostream>

using namespace std;

int MAP[100][100];
int N;

int main()
{
    cin >> N;
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            cin >> MAP[r][c];
        }
    }
}

또 2차원 배열에서 상하좌우 이동 시에 다음 테크닉을 사용하면 코드가 간결해진다 (간결해질뿐 아니라 가독성도 올라간다.). dr과 dc 배열을 사용하여 상하좌우를 나타냈다. DFS() 내에서 for 문으로 4가지 경우를 순회하여 상하좌우를 나타낼 수 있다. 이렇게 dr, dc 배열을 사용하면 상하좌우 이동 뿐만아니라 대각선 이동이나 체스에서 knight의 이동 등의 더 복잡한 이동도 표현할 수 있다.

#include <iostream>

using namespace std;

int MAP[100][100];
bool visit[100][100];
int N;
bool arrival;

// dr, dc 배열을 이용하여 상하좌우 표현. 이 경우 정확히는 좌우상하이다.
// 문제에 따라 특정 방향으로 먼저 향해야 이득인 경우가 있다
// (pruning을 통해 DFS 탐색 횟수가 줄어드는 경우).
// 이 경우 해당 방향으로 먼저 이동하도록 dr, dc 배열의 값을 변경해야한다.
int dr[4] = { 0, 0, -1, 1 };
int dc[4] = { -1 ,1, 0, 0 };

void DFS(int r, int c);

int main()
{
    freopen("input.txt", "r", stdin);
    cin >> N;
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            cin >> MAP[r][c];
        }
    }
    DFS(0, 0);	// (0, 0)에서 출발하는 문제

    return 0;
}

void DFS(int r, int c)
{
    if (arrival) return;
    
    if (r == N - 1 && c == N - 1) {
        cout << "N-1, N-1에 도달하였습니다.";
        arrival = true;
        return;
    }
    visit[r][c] = true;

    // 네 방향에 대해 탐색
    for (int d = 0; d < 4; d++) {
        int nextr = r + dr[d];
        int nextc = c + dc[d];

        if (nextr < 0 || nextr >= N || nextc < 0 || nextc >= N) {
            // 경계를 넘어서는 경우
            continue;
        }

        if (visit[nextr][nextc] == false)
            DFS(nextr, nextc);
    }
    visit[r][c] = false;
}

경계를 표시하는 다른 방법으로 특정 숫자로 배열을 감싸는 방법이 있다. 아래 코드에서 init()을 참고하자. 문제에 따라 이것이 더 효과적일 수 있을 듯 하다 (예를 들어 벽이 0, 길이 1인 경우, 0으로 배열을 감싸고 0을 만나면 더 진행하지 못하게 하면 된다.). 이 경우 배열의 1부터 N 엔트리까지 값을 입력받는다. 다만 MAP의 내용에 포함되는 숫자를 경계값으로 사용하지 않도록 주의하자.

#include <iostream>

using namespace std;

int MAP[102][102];
bool visit[102][102];
int N;
bool arrival;

int dr[4] = { 0, 0, -1, 1 };
int dc[4] = { -1 ,1, 0, 0 };

void DFS(int r, int c);
void init();

int main()
{
    freopen("input.txt", "r", stdin);
    cin >> N;
    for (int r = 1; r <= N; r++) {
        for (int c = 1; c <= N; c++) {
            cin >> MAP[r][c];
        }
    }

    init();

    DFS(1, 1);	// (0, 0)이 아닌 (1, 1)에서 출발한다.

    return 0;
}

void init()
{
    for (int i = 0; i <= N + 1; i++) {
        MAP[i][0] = 0;
        MAP[i][N + 1] = 0;
        MAP[0][i] = 0;
        MAP[N + 1][i] = 0;
    }
}

void DFS(int r, int c)
{
    if (arrival) return;

    if (r == N && c == N) {
        cout << "N, N에 도달하였습니다.";
        arrival = true;
        return;
    }

    visit[r][c] = true;

    // 네 방향에 대해 탐색
    for (int d = 0; d < 4; d++) {
        int nextr = r + dr[d];
        int nextc = c + dc[d];

        // MAP[][]이 0이 아닌지 확인한다. 경계를 일일이 검사할 필요가 없다.
        if (MAP[nextr][nextc] != 0 && visit[nextr][nextc] == false)
            DFS(nextr, nextc);
    }

    visit[r][c] = false;
}