[백준] 1987번 : 알파벳

1987번: 알파벳

# 문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

# 입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

# 출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

# 예제 입력

2 4

CAAB

ADCB

# 예제 출력 

3

---

[DFS + 백트래킹 (+DP도 할 수 있으나 의미 없음)]

문제의 난이도 자체는 크게 어렵지 않으나, 종종 실수가 있을 수 있고 백트래킹을 쓴다면 특히 잡아내기가 쉽지 않아 엉뚱한 곳에서 시간을 잡아먹는 문제가 될 수 있다. 나같은 경우 특정 칸에 문자열을 갖는지 체크하기 위해 String 객체를 사용했었는데 이는 곧 시간 초과로 이어진다. 따라서 String.contains()를 사용하기 보다, Set 컬렉션을 사용하는 것이 바람직하다. 

 

그리고 시작 지점을 카운팅 하는 것을 잊지말아야 한다. 

 

특정 정점에 도착했을 때 항상 최적해인지를 알 수 없으므로 백트래킹을 이용하는 것이 좋다고 생각된다.

    static void DFS(int y, int x){

        visit[y][x] = true; //방문
        str.add(map[y][x]); //set에 문자열 추가
        cnt++;

        for(int a=0; a<4; a++){
            int ny = y+Y[a];
            int nx = x+X[a];

            if((ny>=0 && ny <r) && (nx>=0 && nx<c) && !str.contains(map[ny][nx]) && !visit[ny][nx]) {
                max = Math.max(max, cnt);
                DFS(ny, nx);
            }
        }
        cnt--;
        str.remove(map[y][x]); //set에서 제거
        visit[y][x] = false; //방문 해제
    }

# Code </>

public class Main {

    static int[] X = {1, -1, 0, 0};
    static int[] Y = {0, 0, -1, 1};
    static String[][] map = new String[21][21];
    static boolean[][] visit = new boolean[21][21];
    static int r, c, max = 1, cnt=1;
    static Set<String> str = new HashSet<>();

    static void DFS(int y, int x){

        visit[y][x] = true;
        str.add(map[y][x]);
        cnt++;

        for(int a=0; a<4; a++){
            int ny = y+Y[a];
            int nx = x+X[a];

            if((ny>=0 && ny <r) && (nx>=0 && nx<c) && !str.contains(map[ny][nx]) && !visit[ny][nx]) {
                max = Math.max(max, cnt);
                DFS(ny, nx);
            }
        }
        cnt--;
        str.remove(map[y][x]);
        visit[y][x] = false;
    }

    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());

        for(int i=0; i<r; i++) {
            String[] str = br.readLine().split("");
            for (int j=0; j<c; j++)
                map[i][j] = str[j];
        }

        DFS(0, 0);
        System.out.println(max);
    }
}