[백준-1987]-[DFS-백트래킹]-알파벳

문제링크 : https://www.acmicpc.net/problem/1987

---

이문제를 어떻게 접근할까 하다가 간단하겠지 하고 BFS로 풀었는데 절대 BFS풀면 안된다더라..

그 이유는 동시에 같은 레벨의 다른 접점을 접근하기 때문에 만약 2레벨의 같은 알파벳이 있으면 방문 여부를 파악하기가 힘들다. 

백트래킹으로 가능한 모든 방향을 접근하고 지나간 최대 칸수를 출력해주면 된다. 

말이 쉽지 참 힘들었다. 

예제는 항상 답이 나오는데 제출을 하면 항상 문제였다. 

내가 푼 문제에 반례가 어떤게 있을까 하다가 스스로 예제를 만들어 보았다. 

이것만 통과하면 제출해도 정답이 나올거 같다.. 

내가 생각해낸 예제는 아래 표다.

A	B	B	C
E	C	E	D
F	G	D	H

만약 단순한 DFS만으로 결과를 도출해낸다면 최대 길이는 6이 나온다.

보통 상 , 우, 하, 좌 순으로 DFS를 호출한다고 하면.. 

암만 해도 최대 6까지 밖에 나오지 않았다. 

하지만 결과는 8이 나와야 한다. 

A -> B -> C -> E -> F -> G -> D -> H

예제 만드는데 오래 걸렸다.. 

이 부분만 통과한다면 된다.

힌트로 백트래킹을 이용하면 된다고 했지만 백트래킹 문제를 많이 풀지 않아서 도저히 길이 안보였다. 

내가 감을 제대로 잡지 못했던 이유는 visited의 활용이었다. 

분명 하나의 알파벳에 한번 접근하면 visited는 계속 true이고 접근을 하지 못하는데 어떻게 다른 길을 찾아가지?? 

방법은 가능했다. DFS는 하나의 접점을 기준으로 가능한 끝까지 탐색을 하는데 이 탐색이 끝나면 다른 길에서도 visited 를 사용하게 초기화를 시켜 주면 되는 거였다. 

카운트도 본인의 탐색이 끝나면 본인 전에서 다른 길로 계산 할 수 있게 1을 줄여주는 것으로 백트래킹이 이루어지는 것이었다. 

말로는 엄청 어렵다.. 어떻게 설명을 해야 되는지 아직 지식이 부족해서 설명은 자세히 할 수 가 없지만 그림으로 다시 설명을 해보려고 한다. 

A	B	B	C
E	C	E	D
F	G	D	H

현재 위치 (3, 4)

현재 visited A = true, B = true, C = true, D = true,  E = true, F = false, G = false, H = true

현재 step = 6

최대 step = 6

위의 길로 총 6개의 칸을 밟았다. 

마지막 접점 H에서는 더이상 갈 수 있는 길이 없으므로 이전 좌표 D 가 다른 길을 선택했을때 값이 꼬이지 않게 visited 정보와 카운트를 초기화 시켜주는 것이다. 

A	B	B	C
E	C	E	D
F	G	D	H

현재 위치 (2, 4)

현재 visited A = true, B = true, C = true, D = true,  E = true, F = false, G = false, H = false

현재 step = 5

최대 step = 6

하지만 D 에서도 갈 수 있는 길은 없고 다시 초기화

A	B	B	C
E	C	E	D
F	G	D	H

현재 위치 (2, 3)

현재 visited A = true, B = true, C = true, D = false,  E = true, F = false, G = false, H = false

현재 step = 5

최대 스탭 = 6

여기서는 아래 D로 갈수 있다. 이쪽길로 가보자

A	B	B	C
E	C	E	D
F	G	D	H

현재 위치 (3, 1)

현재 visited A = true, B = true, C = true, D = true,  E = true, F = true, G = true, H = false

현재 step = 7

최대 step = 7

최대 스텝수가 7이다 최대 스템수를 변경해준다.

더이상 갈 길이 없으니깐 계속 visited 와 step 을 초기화 해준다.

A	B	B	C
E	C	E	D
F	G	D	H

현재 위치 (2, 2)

현재 visited A = true, B = true, C = true, D = false,  E = false, F = false, G = false, H = false

현재 step = 3

최대 step = 7

이제 왼쪽의 E로 접근 하고 동일한 방법으로 E -> F-> G -> D -> H 로 탐색을 하면 된다.

그럼 최대 step은 8이 나온다. 

또 다른 최대 경로가 있을 수 있기에 계속해서 본인의 탐색이 끝나면 visited와 step을 카운트 해주면 된다. 

그렇게 DFS가 돌고 돌아 맨 처음 (1, 1)이 본인의 visited와 step을 초기화 하면서 DFS는 종료 되게 된다. 

정말 이해하기 힘들었던 만큼 설명하기도 엄청 힘든거 같다. 

하지만 이런문제가 알고리즘 문제의 대부분일텐데 더 많은 문제 유형을 풀면서 문제의 길을 유추하는 시간을 정확하고 빠르게 할 수 있게 단련이 필요해보인다. 

추가로 알파벳의 아스키 코드로 인덱스를 선언했다.

A의 아스키 코드는 65 고 Z의 아스키 코드는 90 이다. 

입력 받을때 모든 알파벳의 아스키 코드에 65를 뺀 값으로 인덱스를 구성하고 배열도 동일하게 구성했다. 

그래서 A는 0번 인덱스를 Z는 25번 인덱스를 부여 받는다. 

나머지 알파벳은 그 사이 알파벳 순서대로 인덱스를 부여받는다. 

각설하고 마지막 소스를 올리면서 이번 문제도 마친다. 

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static int ROW;
    public static int COL;
    public static int[][] arr;
    
    public static int[] dy = {-1, 1, 0, 0}; // 상하 좌우;
    public static int[] dx = {0, 0, -1, 1};
 
    public static boolean[] visited;
    
    public static int step = 1;
    public static int max_step = 1;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        ROW = Integer.parseInt(st.nextToken());
        COL = Integer.parseInt(st.nextToken());
        arr = new int[ROW][COL];
        
        for(int i=0; i < ROW; i++) {
            String str = br.readLine();
            for(int j=0; j < COL; j++) {
                arr[i][j] = (int)str.charAt(j) - 65;
            }
        }
        
        visited = new boolean[26];
        dfs(0, 0);
        System.out.println(max_step);
    }
    
    public static void dfs(int y, int x) {
        int alpha = arr[y][x];
        visited[alpha] = true;
        
        for(int i=0; i < 4; i++) {
            int yy = dy[i] + y;
            int xx = dx[i] + x;
            
            if(yy < 0 || xx < 0 || yy >= ROW || xx >= COL) continue;
            
            int nextAlpha = arr[yy][xx];
            if(visited[nextAlpha]) continue;
            
            max_step = Math.max(max_step, ++step);
            
            dfs(yy, xx);
        }
        // 여기서 초기화 하지 않으면 다른 경로에서 접근 할 수 없다.
        step --;
        visited[alpha] = false;
    }
}