[백준]1987. 알파벳 - Java

📄 링크

boj 1987. 알파벳

---

💡 문제 분석

• 모든 알파벳을 한 번씩만 지날 수 있기 때문에 , A ~ Z까지 26개의 알파벳을 체크하기 위해 불린 배열을 만듭니다
• 시작지점부터 dfs를 돌며 현재 칸에서 갈 수 있는 4방향 중 가장 큰 값이 답입니다

• bfs를 사용하게 된다면 모든 경로를 탐색하지 않아서 실패하게 됩니다

---

⌨️ 코드

public class _1987_알파벳 {
    static int r, c;
    static int[] dy = {-1, 0, 1, 0}, dx = {0, 1, 0, -1};
    static char[][] s;
    static boolean[] chk;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        r = sc.nextInt(); c = sc.nextInt();
        s = new char[r][c];
        chk = new boolean[26];
        for(int i = 0; i < r; i++)
            s[i] = sc.next().toCharArray();
        chk[s[0][0] - 'A'] = true;
        System.out.println(dfs(0, 0));
    }

    static int dfs(int y, int x) {
        int ret = 1;
        for(int d = 0; d < 4; d++) {
            int ny = y + dy[d], nx = x + dx[d];
            if(ny >= r || nx >= c || ny < 0 || nx < 0 || chk[s[ny][nx] - 'A']) continue;
            chk[s[ny][nx] - 'A'] = true;
            ret = Math.max(ret, dfs(ny, nx) + 1);
            chk[s[ny][nx] - 'A'] = false;
        }
        return ret;
    }
}

---

📋 결과