백준 1987(JAVA)

문제

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

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

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

풀이

무지성으로 bfs로 했다. 문제를 자세히 살피지못하고.. 이문제는 무조건 깊이우선탐색 dfs로 풀어야한다.!!!
왜 그런지 알아보자. 같은 알파벳을 두번 지날수가없다. 즉, 한번 지난 알파벳은 또 지날수가 없다. bfs는 해당 위치에서 상하좌우를 모두 가는 것이므로 하나의 동작이라고 할수 없다. dfs로 상하좌우중 하나만 선택해서 가는 것이 하나의 동작이므로 dfs로 풀어야한다.

그리고 또! 이문제는 백트래킹과 관련이있다. 방문한 위치를 한번 방문했다고 방문처리를 하고 끝나는게 아니라 다시 방문을 할수 있다는게 이문제의 핵심이다.
이문제는 방문한 위치보단 경로가 중요한 dfs + 백트래킹 문제이다.

최대한 많이 말이 움직여야하므로 알파벳을 한번씩 사용하며 움직이려면 전에 실패한 경로들의 위치를 사용해야한다.

즉, dfs로 풀되 한번 방문했다고 다시 방문하지 않는게 아니라 방문 해제를 하는 로직이 필요하다.

코드

package baekjoon.그래프탐색;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main1987 {
    static int R, C;
    static int[][] board;
    static boolean[] visited = new boolean[26];
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int max = -1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        board = new int[R][C];
        for(int i = 0; i < R; i++){
            String str = br.readLine();
            for(int j = 0; j < C; j++){
                board[i][j] = str.charAt(j) - 65;
            }
        }
        dfs(0, 0, 0);

        System.out.println(max + 1);

    }
    static void dfs(int x, int y, int count){
        visited[board[x][y]] = true;
        max = Math.max(max, count);
        for(int i = 0; i < 4; i++){
            int nextX = x + dx[i];
            int nextY = y + dy[i];

            if(nextX < 0 || nextX >= R || nextY < 0 || nextY >= C) continue;
            if(visited[board[nextX][nextY]]) continue;

            dfs(nextX, nextY, count + 1);
        }
        visited[board[x][y]] = false;
    }
}