[java 백준] 골드 4/ 1987번 알파벳

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

1987번: 알파벳

 

import java.util.Scanner;
 
public class Main {
    public static int r, c;
    public static int arr[][];
 
    public static int max = 0;
    
 
    public static boolean check[] = new boolean[27];
 
    public static void DFS(int i, int j, int cnt) {
 
        if (check[arr[i][j]]) { // 중복되는 알파벳이 나오는 경우 리턴
            if (cnt > max) {
                max = cnt;
            }
            return;
        } else {
 
            check[arr[i][j]] = true;
            // 좌
            if (j - 1 >= 0) {
                DFS(i, j - 1, cnt + 1);
            }
            // 우
            if (j + 1 < c) {
                DFS(i, j + 1, cnt + 1);
            }
            // 상
            if (i - 1 >= 0) {
                DFS(i - 1, j, cnt + 1);
            }
            // 하
            if (i + 1 < r) {
                DFS(i + 1, j, cnt + 1);
            }
            // 같은 알파벳이 나오면 부모노드로 돌아가야!, 다른 루트 탐색
            check[arr[i][j]] = false;
 
        }
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        r = sc.nextInt();
        c = sc.nextInt();
 
        arr = new int[r + 1][c + 1];
 
        for (int i = 0; i < r; i++) {
            String s = sc.next();
            for (int j = 0; j < c; j++) {
 
                arr[i][j] = s.charAt(j) - 'A';
 
            }
        }
 
        DFS(0, 0, 0);
        System.out.println(max);
 
    }
 
}
 

 

백트래킹을 할 때 리턴하는 기준 (즉 한 turn이 끝나는 기준)이 행과 열이 r과 c보다 커질 때로 생각했는데

역시나 틀렸다 ^^ 그래서 다른 사람들이 쓴 코드를 찾아봤는데 알파벳이 중복으로 나왔을때를 기준으로 리턴을 해줬다. 특히 백트래킹 문제 특징이 이미 현재 노드를 방문했다면 부모노드로 돌아와야한다는 특징이 있다. (경로 재탐색 위함)

그래서 꼭 마지막에 checek[arr[i][j]]=false 해줘야한다! 만약 이 경로가 먹히지 않으면 다시 부모노드로 돌아와 다른 경로를 탐색해야하기 때문에 현재 탐색한 이력을 지워줘야하기 때문이다.

이 얘기를 왜했냐면 부모 노드로 돌아와야한다는 기준(리턴의 기준) 이 바로 알파벳이 중복될때이기 때문이다!  사실 그러니까 이 알고리즘 이름이 백트래킹인 것 같은데 난 백트래킹 문제를 7번째 푸는 지금에서야 깨달았다..ㅋㅋㅋㅋ ㅜㅜㅜㅜ

 

내 코드는 왜 틀렸을까?

 

import java.util.Scanner;
 
public class Main {
    public static int r, c;
    public static int arr[][];
    public static boolean visited[][];
    public static int max = 0;
    public static int[] dX = { -1, 1, 0, 0 };
    public static int[] dY = { 0, 0, -1, 1 };
    public static int check[];
 
    public static void DFS(int i, int j, int cnt) {
 
        if (cnt > max) {
            max = cnt;
        }
        if (i >= r && j >= c) {
            return;
        } else {
            if (check[arr[i][j]] == 0 && !visited[i][j]) {
 
                visited[i][j] = true;
                check[arr[i][j]]++;
                for (int k = 0; k < 4; k++) {
                    int changeX = i + dX[k];
                    int changeY = j + dY[k];
                    if (changeX >= 0 && changeY >= 0 && changeX < r && changeY < c) {
                        DFS(changeX, changeY, cnt + 1);
                    }
 
                }
 
            }
        }
 
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        r = sc.nextInt();
        c = sc.nextInt();
 
        arr = new int[r + 1][c + 1];
        visited = new boolean[r][c];
 
        for (int i = 0; i < r; i++) {
            String s = sc.next();
            for (int j = 0; j < c; j++) {
 
                arr[i][j] = s.charAt(j) - 'A';
 
            }
        }
 
        check = new int[27];
 
        DFS(0, 0, 0);
        System.out.println(max);
 
    }
 
}

 

visited 2차원 배열 만들어서 똑같은 인덱스 방문했는지 확인해줬는데 이건 의미가 1도 없다. 그냥 알파벳 중복이 중요

앞서 말했듯이 부모노드로 돌아오는 기준을 아예 잘못잡았다.