[백준 1978] 알파벳 (Java) - DFS, 백트래킹

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

알파벳

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

2 4
CAAB
ADCB

예제 출력 1 복사

3

예제 입력 2 복사

3 6
HFDFFB
AJHGDH
DGAGEH

예제 출력 2 복사

6

---

풀이

HashSet을 활용한 풀이

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

public class Main {
    static int R,C;
    static String[][] A;
    static boolean[][] visited;
    static int count = 0;
    static HashSet<String> passed = new HashSet<>();
    static int[] dx = {-1, 1, 0, 0}; // 상 하 좌 우 좌표
    static int[] dy = {0, 0, -1, 1};
    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()); // 가로 칸 (열)
        A = new String[R+1][C+1]; // 보드 (행, 열 모두 1부터 시작)
        visited = new boolean[R+1][C+1]; // 방문배열

        // 보드 정보 입력받기
        for (int i=1; i<R+1; i++){
            String[] alphabets = br.readLine().split("");
            for (int j=1; j<C+1; j++){
                A[i][j] = alphabets[j-1];
            }
        }

        DFS(1,1);

        System.out.println(count);
    }
    private static void DFS(int i, int j){
        passed.add(A[i][j]); // 현재 알파벳 추가
        count = Math.max(count, passed.size()); // 이동칸수 최대값으로 업데이트

        for (int k=0; k<4; k++){ // 현재 좌표에서 상하좌우 좌표 탐색
            int nx = i + dx[k];
            int ny = j + dy[k];

            if (isIn(nx,ny) && !visited[nx][ny] && !passed.contains(A[nx][ny])){
                visited[nx][ny] = true;
                DFS(nx, ny); // 탐색좌표로 재귀호출
                visited[nx][ny] = false;
            }
        }
        passed.remove(A[i][j]); // 백트래킹
    }
    private static boolean isIn(int x, int y){
        return x>0 && y>0 && x<=R && y<=C;
    }
}

• DFS를 활용한 문제
• 상하좌우 좌표를 탐색하며 유효한 좌표일 시 깊이우선 탐색을 수행한다.
• 이미 지나온 알파벳에 해당하는지 알아보기 위해 hash set을 이용했다.
• 정답은 통과하지만, 메모리/시간 비효율적 풀이이다.
• 어차피 알파벳은 26개만 있으므로 26크기의 boolean 배열을 선언해서 이미 지나온(선택한) 알파벳인지 true/false 기준으로 확인만 하면 더 효율적으로 풀이 할 수 있다.

boolean배열 활용 풀이

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

public class Main {
    static int R,C,max = 0;
    static char[][] board;
    static boolean[] used = new boolean[26]; // A ~ Z 사용여부
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

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

        for (int i=0; i<R; i++){
            String alphabets = br.readLine();
            for (int j=0; j<C; j++){
                board[i][j] = alphabets.charAt(j);
            }
        }

        used[board[0][0] - 'A'] = true; // 첫 시작 알파벳 방문처리
        DFS(0,0,1);
        System.out.println(max);
    }
    private static void DFS(int x, int y, int depth){
        // 이동칸 수 최댓값 비교
        max = Math.max(max, depth);

        for (int k=0; k<4; k++){ // 현재 좌표 상하좌우 좌표 탐색
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx>=0 && ny>=0 && nx<R && ny<C){
                int idx = board[nx][ny] - 'A'; // 탐색좌표 알파벳 index
                if (!used[idx]){
                    used[idx] = true;
                    DFS(nx, ny, depth+1);
                    used[idx] = false; // 백트래킹
                }
            }
        }
    }
}

• 26크기의 boolean배열을 선언해서 선택한 알파벳에 체크를 한다.
• 이동칸 수는 depth파라미터를 활용해서 비교할 수 있다.

메모리 / 시간 비교

위는 boolean 배열을 활용한 풀이이고, 아래는 hash set을 활용한 풀이이다.

메모리에 있어서는 20배 차이, 시간은 3배 차이가 난다.

앞으로 메모리/시간 효율적인 풀이에 대해서 다시 생각해보자^^