백준 1987번 알파벳 :: 마이구미

이번 글은 백준 알고리즘 문제 1987번 "알파벳" 을 다뤄본다.

문제 풀이는 DFS를 응용하여 해결할 수 있다.

DFS, BFS - http://mygumi.tistory.com/102

Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc

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

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

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

결국 문제에서 원하는 건, 서로 다른 알파벳의 최대 경로를 구하면 된다.

BFS를 이용하면, 모든 분기점을 다 검사하기 때문에, 알파벳 방문 여부를 체크하기가 까다로웠다.

그렇기에,  하나의 정점을 기준으로 깊이 끝까지 탐색하는 DFS를 이용하였다.

기본적인 DFS를 이용하면 된다.

깊이 탐색 후, 더이상 탐색할 수 없을 경우, 백트래킹이 일어나는 정점들은 다시 방문하지 않았다고 표시해야한다.

그래야 백트래킹 된 정점을 기준으로 다시 DFS를 통해 방문할 수 있기 때문이다.

이것은 아래 예를 통해 다시 확인해보자.

ABCD
BBDA
BBEB

A->B->C->D 까지 탐색 후 A가 이미 방문한 알파벳이기 때문에, DFS가 끝이 난다.

움직인 칸은 4칸이 되고, 백트래킹이 일어나서 C까지 돌아오게 된다.

ABCD
BBDA
BBEB

C로 돌아온 시점에서는 2행 3열을 탐색할 경우 D는 방문하지 않았기 때문에 탐색해야한다.

여기서 이전 탐색을 통해 알파벳 D는 방문했었다.

하지만 D 방문 여부를 가지고 있다면, DFS가 일어날 수 없게 된다.

또한, D까지 방문한 정점이 아니기 때문에, 움직인 칸은 3이 된다.

결국 이러한 방문 여부와, 움직인 칸을 정점에 맞춰 진행해야한다는 것이다.

백트래킹이 일어날 때, 일어나는 정점에 대해 방문 여부를 없애고, 움직인 칸도 빼면 된다.

기본적인 DFS 코드에서 이러한 처리만 추가된 것이다.

이 과정은 전체 코드에서 아래 부분을 확인하길 바란다.

--cnt;
visited[idx] = false;

static int[] dx = { -1, 0, 1, 0 };
static int[] dy = { 0, -1, 0, 1 };
static int r;
static int c;
static int cnt = 1;
static int ans = 1;
 
private void solve() {
    // http://mygumi.tistory.com/186
    r = sc.nextInt();
    c = sc.nextInt();
    char[][] map = new char[r][c];
    boolean[] visited = new boolean[26];
 
    for (int i = 0; i < r; i++) {
        map[i] = sc.readLine().toCharArray();
        for (int j = 0; j < c; j++) {
            map[i][j] = (char) (map[i][j] - 'A');
        }
    }
 
    dfs(map, visited, 0, 0);
    System.out.println(ans);
}
 
public static void dfs(char[][] map, boolean[] visited, int y, int x) {
    int idx = map[y][x];
 
    visited[idx] = true;
 
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
 
        if (-1 < nx && nx < c && -1 < ny && ny < r) {
            int next = map[ny][nx];
 
            if (!visited[next]) {
                ans = Math.max(++cnt, ans);
                dfs(map, visited, ny, nx);
            }
 
        }
    }
 
    // 초기화
    --cnt;
    visited[idx] = false;
}