[BOJ] 1987 : 알파벳 (Java)

https://www.acmicpc.net/problem/1987

1987번: 알파벳

걸린 시간 : 23분 22초

---

전형적인 백트래킹 문제이다. 단, 재귀함수 호출 시 알파벳을 지나갔는지에 대한 검사도 해야 한다.

이 검사에는 HashSet 자료구조를 썼다.

정답 코드

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

public class BOJ1987 {

    static int R, C;
    static String[] board = new String[21];
    static boolean[][] vis = new boolean[21][21];
    static int answer = 1;
    static int pass = 1;
    static HashSet<Character> hashSet = new HashSet<>();
    static int[] di = {-1, 0, 0, 1};
    static int[] dj = {0, -1, 1, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        R = Integer.parseInt(input[0]);
        C = Integer.parseInt(input[1]);
        for (int i = 0; i < R; i++) {
            board[i] = br.readLine();
        }
        vis[0][0] = true;
        hashSet.add(board[0].charAt(0));
        dfs(0, 0);
        System.out.println(answer);
    }

    private static void dfs(int ci, int cj) {
        for (int k = 0; k < 4; k++) {
            int ni = ci + di[k];
            int nj = cj + dj[k];
            if (ni < 0 || ni >= R || nj < 0 || nj >= C || vis[ni][nj]) continue;
            if (hashSet.contains(board[ni].charAt(nj))) continue;
            pass++;
            answer = Math.max(pass, answer);
            vis[ni][nj] = true;
            hashSet.add(board[ni].charAt(nj));
            dfs(ni, nj);
            pass--;
            vis[ni][nj] = false;
            hashSet.remove(board[ni].charAt(nj));
        }
    }
}