https://www.acmicpc.net/problem/1987
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.
말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.
첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.
첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.
2 4
CAAB
ADCB
3
3 6
HFDFFB
AJHGDH
DGAGEH
6
5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH
10
#include <iostream>
#define MAX 20
using namespace std;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int answer = 0;
int R, C;
bool visit[26];
char MATRIX[MAX][MAX];
void DFS(int X, int Y, int count){
answer = max(answer, count);
for(int i = 0; i < 4; i++){
int nx = X + dx[i];
int ny = Y + dy[i];
if(0 <= nx && nx < R && 0 <= ny && ny < C && !visit[MATRIX[nx][ny] - 'A']){
visit[MATRIX[nx][ny] - 'A'] = true;
DFS(nx, ny, count + 1);
visit[MATRIX[nx][ny] - 'A'] = false;
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> R >> C;
for(int i = 0; i < R; i++){
for(int j = 0; j < C; j++) cin >> MATRIX[i][j];
}
visit[MATRIX[0][0] - 'A'] = true;
DFS(0, 0, 1);
cout << answer << '\n';
}
BFS로 풀다가 시간초과가 났다.
BFS의 최대 단점이 뭘까? 확실히 속도 면에서 불리할 수 있다. 상황에 따라 다르겠지만 이번 문제처럼 특정 방향 기준으로 서치해야 할 경우에 유리하다고 볼 수는 없다.
즉 한쪽 방향으로 쭉 서치하는 게 아니라 매 시점마다 4방향을 모두 서치하다보니까 간섭이 생길 수도 있다. 이러한 비슷한 문제를 풀 때 이 점을 간과해서 많이 틀리곤 했던 기억이 난다.
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int answer = 0;
int R, C;
bool visit[26];
char MATRIX[MAX][MAX];
void DFS(int X, int Y, int count){
answer = max(answer, count);
for(int i = 0; i < 4; i++){
int nx = X + dx[i];
int ny = Y + dy[i];
if(0 <= nx && nx < R && 0 <= ny && ny < C && !visit[MATRIX[nx][ny] - 'A']){
visit[MATRIX[nx][ny] - 'A'] = true;
DFS(nx, ny, count + 1);
visit[MATRIX[nx][ny] - 'A'] = false;
}
}
}
4방향을 탐색하는것은 똑같다. 차이가 있다면 해당 시점에서 4방향을 모두 탐색하는 게 아니라 1방향 씩 가능한 모든 경우를 탐색하고 나와서 다시 다음 방향을 탐색하는 것.
이 테크닉에 익숙해져야 한다. 생각보다 BFS를 써야 할 것 같음에도 이러한 테크닉을 통해 DFS로 탐색을 해야 답이 나오는 경우를 많이 만나보았다.