백준 1987번 알파벳 자바 풀이

❓문제

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

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

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

---

🔠 입력

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

---

🖨️출력

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

---

✍️ 예제 입력

2 4
CAAB
ADCB

✔️ 예제 출력

3

✍️ 예제 입력

3 6
HFDFFB
AJHGDH
DGAGEH

✔️ 예제 출력

6

✍️ 예제 입력

5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

✔️ 예제 출력

10

 

---

💡해설

알파벳은 26자리이므로 배열을 만들어놓고 이미 한 번 지나온 알파벳의 자리는 true로 한다.

 

계속 이어서 가야하기 때문에 지나간 자리를 되돌아가는 건 안된다.

더이상 갈 수 없으면 갔던 자리를 다시 false로 하고 다른 길을 찾는다.

max값을 찾아서 출력한다. 

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

public class Main {

    static int[][] arr;
    static int R, C;
    static int dx[] = { 1, 0, -1, 0 };
    static int dy[] = { 0, 1, 0, -1 };
    static boolean[] visited = new boolean[26];
    static Set<Integer> sets = new HashSet<>();
    static int max = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();

        R = Integer.parseInt(input.split(" ")[0]);
        C = Integer.parseInt(input.split(" ")[1]);

        arr = new int[R][C];

        String value;
        for (int i = 0; i < R; i++) {
            value = br.readLine();
            for (int j = 0; j < C; j++) {
                arr[i][j] = value.charAt(j) - 'A';
                System.out.println(arr[i][j]);
            }
        }

        findWay(0, 0, max);
        System.out.println(max);
    }

    private static void findWay(int x, int y, int count) {
        if (visited[arr[x][y]]) {
            max = Math.max(max, count);
        } else {
            visited[arr[x][y]] = true;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx > -1 && ny > -1 && nx < R && ny < C) {
                    findWay(nx, ny, count + 1);
                }
            }
            visited[arr[x][y]] = false;
        }

    }

}