[Java] 백준 BOJ / 1987번: 알파벳

알파벳

문제

---

문제 설명

R X C 로 이루어진 보드에 알파벳들이 적혀있는데 전부 다른 알파벳으로 그래프를 순회했을 때 최대 몇 칸을 지날 수 있는지 구하는 문제이다.

일단 최단거리를 구하는 것이 아니기 때문에 BFS가 아닌 DFS를 사용해야 하고 여러 경로 중 비교를 해야하니 백트래킹을 사용했다.

---

구현

일단 어떤 알파벳을 사용했는지 저장하기 위해 alphabet이라는 ArrayList가 필요하다.

그리고 DFS의 함수 인자에는 처음 시작하는 x좌표, y좌표, 그리고 말이 얼마나 이동했는지 확인 하는 depth를 넘겨준다.

alphabet = new ArrayList<>();

dfs(0, 0, 1);

DFS의 함수 내부에서는 현재 점의 알파벳을 alphabet 배열에 넣어준다.

그 후 현재 단계에서의 depth는 말이 이동한 거리이기 때문에 result 를 갱신해준다.

그 후 nx와 ny를 구하고 해당위치의 알파벳이 사용되지 않았으면 재귀함수에 nx, ny, depth + 1을 넣어준다.

이 과정을 4방향 모두 했다면 alphabet 배열에서 빼서 다른 경로를 탐색할 수 있게 해준다.

---

코드

import javax.sound.sampled.Line;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_1987 {
    static int r, c;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static char[][] board;
    static Queue<Point> queue;
    static ArrayList<Character> alphabet;
    static int result;

    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());

        queue = new LinkedList<>();
        alphabet = new ArrayList<>();

        board = new char[r][c];

        for (int i = 0; i < r; i++) {
            String str = br.readLine();
            for (int j = 0; j < c; j++) {
                board[i][j] = str.charAt(j);
            }
        }

        dfs(0, 0, 1);

        System.out.println(result);
    }

    public static void dfs(int x, int y, int depth) {
        alphabet.add(board[x][y]);
        result = Math.max(result, depth);

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

            if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
                if (!alphabet.contains(board[nx][ny])) {
                    dfs(nx, ny, depth + 1);
                }
            }
        }
        alphabet.remove(Character.valueOf(board[x][y]));
    }
}