[Java] 백준 1987 : 알파벳

[Java] 백준 1987 : 알파벳

 

알파벳 적힌 칸을 한 번씩만 지나서 최대한 몇 칸을 움직일 수 있는가를 구현한다.

 

DFS로 구현할 경우, 각각의 루트에 대해서 지나갈 수 있는 값들 중 최댓값을 출력할 수 있도록 해야한다.

 

특정 루트에 대한 탐색이 끝나면 다음 루트에 대한 탐색도 온전하게 진행되어야 하므로,

dfs의 재귀가 끝날 때 해당 알파벳에 대한 방문 처리를 초기화 해주어야 한다.

방문 처리를 초기화 해주지 않으면 다음 루트에 대한 탐색에 문제가 생기기 때문이다.

 

 

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

public class Main {

    static int R, C;
    static int dx[] = { -1, 1, 0, 0 };
    static int dy[] = { 0, 0, -1, 1 };
    static int [][] map;
    static boolean [] visited = new boolean[26]; // 알파벳 개수
    static int answer = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 입력한 값 map에 할당
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new int[R][C];
        for (int i = 0; i < R; i++) {
            String str = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = str.charAt(j) - 'A';
            }
        }
        dfs(0, 0, 0);
        System.out.println(answer);
    }

    public static void dfs(int i, int j, int count) {
        if (visited[map[i][j]]) {  // 방문을 했었다면
            answer = Math.max(answer, count); // 정답을 갱신하고 리턴
        }
        else {
            visited[map[i][j]] = true;
            for (int k = 0; k < 4; k++) {
                int x = i + dx[k];
                int y = j + dy[k];

                if (x >= 0 && y >= 0 && x < R && y < C) {
                    dfs(x, y, count + 1);
                }
            }
            visited[map[i][j]] = false;
        }

    }
}