[백준 1987] 알파벳

문제

---

접근

• DFS 탐색을 통해서 말을 이동할 수 있는 경로 탐색
  • 이때, alphabets 배열을 통해서 중복된 알파벳의 경로로 가지 않도록 해야 한다고 생각하였다.
  • alphabets 배열을 A~Z까지의 26의 크기를 가진 배열로 설정하였다.
  • 해당 알파벳의 정수 값에서 'A'의 정수값을 빼면 해당 알파벳의 인덱스 값이 되기 때문에 탐색한 경우 해당 배열 인덱스에 위치한 값을 true로 변환해주었다.
• 백트래킹!!!!
  • 알파벳을 탐색하면서 중복 처리를 한 map에서 말의 움직임을 count한다.
  • 이때 다른 경로를 탐색하기 위해 중복 처리를 한 부분을 다시 원복시킨다.
  • 원복 시킨 것에서 다른 경로로 탐색하고 다시 중복처리를 진행하면서 말의 움직임을 또 count한다.
  • 탐색할 때마다 maxCount를 최댓값으로 갱신해주면서 최종 값을 구할 수 있다.

---

코드

import java.util.*;
import java.io.*;

public class Main {
    static char[][] map;
    static int R, C;
    static boolean[] alphabets;
    static int maxCount;
    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());

        map = new char[R][C];
        alphabets = new boolean[26];
        for (int i = 0; i < R; i++) {
            String row = br.readLine();
            map[i] = row.toCharArray();
        }

        maxCount = 0;
        dfs(0, 0, 1);
        System.out.println(maxCount);

    }


    static void dfs(int x, int y, int count) {
        int index = map[x][y] - 'A';
        alphabets[index] = true;
        maxCount = Math.max(maxCount, count);

        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 && !alphabets[map[nx][ny] - 'A']) {
                dfs(nx, ny, count + 1);
            }
        }
        // 백트래킹
        alphabets[index] = false;

    }
}