[Gold IV][JAVA]1987번:알파벳

[Gold IV]1987번:알파벳 - 풀어보기

문제 풀이  

백트래킹을 이용한 DFS탐색 문제이다. 같은 알파벳이 나오면 부모노드로 돌아가서 다른 경로를 탐색하여 최대 경로를 찾으면 된다.

📚 조건

• 세로 R, 가로 C ( 1 <= R,C <= 20)
• 결과값 : 아무곳도 가지 못하면 자기자신이 있는 위치만 카운트되므로 1
• 말 이동 : 상하좌우 한칸, 새로 이동한 칸은 지금까지 지나온 알파벳과는 달라야 함

로직

1. 알파벳을 int형으로 변환하여 그래프에 저장한다. map[i][j] = str.charAt(0)-'A';
2. 백트래킹과 DFS탐색을 통해 그래프의 최대 경로를 찾는다.
   1. visited[알파벳숫자] == true, 이미 지나온 알파벳이므로 해당 경로 탐색을 종료하고 경로 길이를 출력한다.
   2. visited[알파벳숫자] == false, 아직 지나지 않은 알파벳이므로 탐색을 계속 진행한다.
   3. 매번 DFS가 실행될 때마다 알파벳의 길이를 max으로 갱신시켜준다.

코드

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

public class Main { //유형: DFS + 백트래킹, 메모리제한: 256 MB, 시간 제한: 2초
    static int R, C;
    static int[][] map;
    static boolean[] visited = new boolean[26];
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static int max = 1;

    public static void main(String argsp[]) 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()); //가로
        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); // (0,0)부터 시작하며, 현재 이동한 위치는 0회

        System.out.println(max);
    }

    public static void dfs(int x, int y, int cnt) {
        if (visited[map[x][y]]) {
            max = Math.max(max, cnt);
            return;
        } else {
            visited[map[x][y]] = true;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx < 0 || ny < 0 || nx >= R || ny >= C)
                    continue;

                dfs(nx, ny, cnt + 1);
            }
        }
        visited[map[x][y]] = false;
    }
}