[JAVA] 백준 1987 알파벳

 

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

 

문제분석

백트래킹 연습용으로 좋을 것 같아서 풀었다. 백트래킹은 뭐니뭐니해도 DFS지...

문제 개념 자체는 굉장히 쉽다. 단순히 말하면, 다른 문자로 이루어진 가장 긴 경로 만들기 라고 볼 수 있다.

set 자료형을 쓰는 게 당연해보이지만, 이 set을 백트래킹에 맞춰 잘 쓰는 것이 관건이다.

 

DFS(4방위로 나아갈 방향 있나 탐색)을 진행하면서, set에 하나씩 더한다. 여기서, 4가지 방향을 다 시도해 본 뒤 반드시 현재 row,col의 문자를 set에서 제거해야 한다. 재귀로 구현한 것 자체가 깊이 우선 탐색이기 때문에, if문 4개를 먼저 도는 것이 아니라 if문 1->그 속 DFS의 if 문 1->... 이렇게 깊이 들어가게 된다. 따라서 마지막(더 나아갈 수 없는 지점) 에 도달했을 때, set에서 해당 문자를 제거해 줘야 바로 위 DFS 함수의 if 문 2로 원활히 탐색할 수 있게 된다. 이 부분이 바로 백트래킹의 핵심이라고 할 수 있다.

 

코드

import java.util.*;
import java.io.*;

public class Main {

    static Set<String> set = new HashSet<>();
    static int max = 1;
    static String[][] arr;
    static int R;
    static int C;

    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());
        arr = new String[R][C];

        for(int i = 0; i < R; i++){
            arr[i] = br.readLine().split("");
        }

        // 시작점은 항상 arr[0][0]
        // "온" 방향 0: 상단, 1: 우단, 2: 하단, 3: 좌단
        DFS(0,0,3);
        DFS(0,0,0);
        System.out.println(max);

    }


    // dirction이 "온 방향" 말함. 0: 상단, 1: 우단, 2: 하단, 3: 좌단
    public static void DFS(int row, int col, int direction){
        // 현재 위치로 못 오는 경우 그냥 return
        int prevSize = set.size();
        set.add(arr[row][col]);
        if(prevSize == set.size()){
            return;
        }
        // direction 방향 빼고, 나머지 방향으로만 가야 함

        if(direction != 0 && row - 1 >= 0){// 상단으로 갈 수 있는 경우
            DFS(row - 1, col,2);
        }
        if(direction != 2 && row + 1 < R){// 하단으로 갈 수 있는 경우
            DFS(row + 1, col, 0);
        }if(direction != 3 && col - 1 >= 0){// 좌단으로 갈 수 있는 경우
            DFS(row, col - 1, 1);
        }
        if(direction != 1 && col + 1 < C){// 우단으로 갈 수 있는 경우
            DFS(row, col + 1, 3);
        }
        // 더 이상 갈 수 있는 곳이 없다면 1. max 업데이트 - set 길이로
        // 2. set에서 arr[row][col] 문자 제외하기 - DFS임
        max = Math.max(max, set.size());
        set.remove(arr[row][col]);

    }
}