[코딩테스트] BFS에서 배열 크기를 +@로 설정하는 이유

BFS에서 배열 크기를 +@로 설정하는 이유

BFS(너비 우선 탐색)를 구현할 때, 배열 크기를 문제에서 주어진 크기보다 +@를 해서 선언하는 경우가 많다. 예를 들어, 문제가 M=100, N=100이라고 하면, 배열을 board[102][102]로 설정하는 방식이다.

 

백준 2583번

풀이 예시

1. 왜 배열 크기를 +2로 설정하는가?

배열 크기를 +2로 설정하는 가장 큰 이유는 배열의 경계를 벗어나는 오류를 방지하기 위해서다. BFS/DFS를 구현할 때, 보통 상하좌우 네 방향으로 탐색하는데, 이때 탐색 과정에서 배열 범위를 벗어날 가능성이 있다.

예제 코드 (BFS 범위 체크)

if (nx < 0 || nx >= M || ny < 0 || ny >= N)
    continue; // 범위를 벗어나면 스킵

위 코드는 (nx, ny)가 배열의 범위를 벗어났을 경우, 즉 nx == M 또는 ny == N이 되면 continue를 해서 다음 탐색으로 넘어가도록 한다. 하지만 배열 크기를 딱 맞게 board[M][N]으로 설정하면 M 또는 ny == N일 때 배열을 초과하여 접근하는 문제가 발생할 수 있다.

이를 방지하기 위해 배열을 M+2, N+2 크기로 선언하면 경계를 체크하는 과정이 더 안전해진다. 즉, board[102][102]로 설정하면, 잘못된 접근이 이루어지더라도 board[100][100]을 벗어나지 않게 된다.

2. 직접 실험해보기 (+2를 하는 이유)

예를 들어, M=5, N=5 크기의 배열을 선언한다고 가정해보자.

배열 크기를 5×5로 설정한 경우

int board[5][5];

• 탐색 범위는 (0부터 4까지), 즉 board[4][4]까지 가능하다.

문제 발생 가능성

• BFS나 DFS를 수행할 때, 이동 가능한 위치가 nx == 5 또는 ny == 5가 되는 순간 board[5][5]에 접근하게 된다.
• 하지만 board[5][5]는 선언되지 않았으므로 런타임 에러 발생 가능성이 있다.

배열 크기를 7×7로 설정한 경우

int board[7][7]; // M=5, N=5이지만 +2 해서 선언

• 탐색 범위는 여전히 (0부터 4까지)지만,
• nx == 5, ny == 5일 경우에도 안전하게 board[5][5]가 존재하므로 에러가 발생하지 않는다.

이 방식의 장점

• 경계값 검사를 할 때 실수를 방지할 수 있다.
• C++은 배열의 범위를 벗어난 접근을 체크하지 않기 때문에, 메모리 접근 오류를 미리 예방 가능하다.

3. 정리 (배열 크기를 +@ 하는 이유)

1. BFS/DFS에서 경계를 체크할 때 실수를 방지하기 위함.
2. nx == M 또는 ny == N이 되어도 런타임 에러가 발생하지 않도록 안전하게 처리.
3. C++에서는 배열의 범위를 넘어서 접근해도 오류 메시지가 발생하지 않고, 이상한 값이 나올 수도 있음. 이를 방지하기 위해 여유 공간을 둠.

그래서 M=100일 때 board[102][102]로 선언하는 것이 일반적이다.