[백준 1987] 알파벳

 

보드에서 모든 경우를 탐색해야 하기 때문에 백트래킹을 활용한다.

 

static boolean alpha[] = new boolean[26];
static boolean visited[][];
static int dr[] = {-1, 1, 0, 0};
static int dc[] = {0, 0, -1, 1};

 

1. 알파벳은 최대 1번만 사용 가능하기 때문에 배열을 만들어 각 알파벳 별로 사용했는지 여부를 체크한다.

2. DFS 도중 같은 지점은 방문할 수 없으므로 방문기록 배열을 만든다.

3. 상하좌우로 이동하기 때문에 방향배열을 만든다.

 

if(!visited[nr][nc] && !alpha[a[nr][nc] - 'A']) {
    visited[nr][nc] = true;
    alpha[a[nr][nc] - 'A'] = true;
    dfs(nr, nc, cnt + 1);
    visited[nr][nc] = false;
    alpha[a[nr][nc] - 'A'] = false;
}

 

완전탐색을 해야하기 때문에 퇴각 탐색을 한다(백트래킹).

 

 

public class Main {
    
    static int R;
    static int C;
    static char a[][];
    static boolean alpha[] = new boolean[26];
    static boolean visited[][];
    static int dr[] = {-1, 1, 0, 0};
    static int dc[] = {0, 0, -1, 1};
    static int max = 0;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        R = sc.nextInt();
        C = sc.nextInt();
        a = new char[R][C];
        visited = new boolean[R][C];
        for(int i=0; i<R; i++)
            a[i] = sc.next().toCharArray();
        
        alpha[a[0][0] - 'A'] = true;
        visited[0][0] = true;
        dfs(0, 0, 1);
        System.out.println(max);
    }
    
    public static void dfs(int r, int c, int cnt) {
        for(int i=0; i<4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if(0 <= nr && nr < R && 0 <= nc && nc < C) {
                if(!visited[nr][nc] && !alpha[a[nr][nc] - 'A']) {
                    visited[nr][nc] = true;
                    alpha[a[nr][nc] - 'A'] = true;
                    dfs(nr, nc, cnt + 1);
                    visited[nr][nc] = false;
                    alpha[a[nr][nc] - 'A'] = false;
                }
            }
        }
        max = Math.max(max, cnt);
    }
}