[JAVA] 백준 골드4 1987 알파벳

 

 

문제 탐색

• 좌측 상단 칸에 위치한 말이 알파벳 보드를
• 상하좌우로 이동하면서
• 최대한 몇 칸을 지날 수 있는지 출력 => 칸을 지날때마다 거리 체크
• 새로 이동한 칸의 알파벳은 지나온 모든 칸의 알파벳과 겹치면 안된다 => 알파벳 방문 처리

 

1. 

public class Main {
    static int r, c, maxLen = 0;  //세로 길이 r, 가로 길이 c, 최대 칸 maxLen
    static char[][] arr;          //알파벳 보드 입력
    static boolean[] visited = new boolean[26];  // 알파벳 A~Z 방문 여부
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

 

2.

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 char[r][c];

        for (int i = 0; i < r; i++) {           //알파벳 보드 입력
            String[] s = br.readLine().split("");
            for (int j = 0; j < c; j++) {
                arr[i][j] = s[j].charAt(0);
            }
        }
        dfs(0,0,1);  //말이 위치한다고 했던 가장 왼쪽 0,0 부터 dfs 순회 시작
        System.out.println(maxLen);
    }

 

public static void dfs(int i, int j, int depth) {
        int alpaIdx = arr[i][j] - 'A';   //알파벳을 인덱스로 방문 관리
        visited[alpaIdx] = true;         //방문처리
        maxLen = Math.max(maxLen, depth);//가장 긴 탐색 칸 수 저장

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

            if(nx>=0 && nx<r && ny>=0 && ny<c) {  //나아갈 칸이 보드 규격에 속하는지
                int nextAlpaIdx = arr[nx][ny] - 'A';
                if(!visited[nextAlpaIdx]) {       //나아갈 칸의 알파벳이 아직 방문전인지
                    dfs(nx, ny, depth+1);         //칸 전진
                    visited[nextAlpaIdx] = false; //dfs 재귀가 종료되면 방문 반환
                }
            }
        }
    }

 

백트래킹

깊이 우선 탐색, 더 이상 나아갈 수 없는 상황에서 그 이전 단계로 복귀하는 과정

 

 

---

완전탐색 추천 문제집

https://www.acmicpc.net/workbook/view/2052