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;
}
