(코테) 백준_1987_알파벳 백트레킹

 

 

 

 

 

 

 

package test;
import java.util.*;
import java.io.*;

/*
범위가 20개씩이니깐    bfs보다 dfs 접근이 좋을듯 
X = {-1,1,0,0} 상하좌우   + 세로
Y = {0,0,-1,1}    상하좌우   + 가로

세로 R 
가로 C 
대문자 CHAR  
(1,1) H   (말 이동 가능 그러나 다음칸이 지금까지 지나온 알파벳 X )   *시작도 +1 로 해야함  

문제 - 말이 지날 수 있는 최대의 칸수  DFS 깊은 탐색 
여러 케이스 필요함.
 
 백트레킹에서 굳이 따지자면 조합?
 
 
 ex)
2 4
CAAB
ADCB

CABBB
DDDBB
BDBBB


 */

public class Backjun_1987 {
    static int r, c, max = 0;
    static char[][] board;
    static boolean[] used = new boolean[26]; // 알파벳 방문 여부
    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++) {
            board[i] = br.readLine().toCharArray();
        }

        used[board[0][0] - 'A'] = true; // 시작 알파벳 사용 처리
        dfs(0, 0, 1); // depth = 1부터 시작
        System.out.println(max);
    }

    public static void dfs(int x, int y, int depth) {
        max = Math.max(max, depth); // 현재까지 최장 경로 갱신

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;

            int alphaIndex = board[nx][ny] - 'A';   //알파벳
            if (!used[alphaIndex]) {
                used[alphaIndex] = true;
                dfs(nx, ny, depth + 1);
                used[alphaIndex] = false; // 백트래킹 (복구)
            }
        }
    }
}

 

 

회고

1. 알파벳을 담을 배열 생각 못함.

2. dfs 호출하면서 count를 길이로 생각 못함.

3.  int alphaIndex = board[nx][ny] - 'A'; 이게 알파벳의 인덱스