https://www.acmicpc.net/problem/1987

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

예제 입출력

• 예제 입력 1

2 4
CAAB
ADCB

• 예제 출력 1

3

• 예제 입력 2

3 6
HFDFFB
AJHGDH
DGAGEH

• 예제 출력 2

6

• 예제 입력 3

5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

• 예제 출력 3

10

Solution

#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로 탐색을 해야 답이 나오는 경우를 많이 만나보았다.