[백준/JAVA] 1987번: 알파벳

📖 문제

1987번: 알파벳

 

 

 

💡  풀이 방식

• 백트래킹 + DFS

 

(0,0)부터 dfs를 한다.

해당 점의 인접한 4방향 탐색을 통해 격자 범위 내에 있고, 지금까지 나온 적 없는 알파벳인 경우 마저 탐색을 진행하며 최대 경로를 찾는다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    static int R,C;
    static int[][] board;
    static boolean[] alphabet = new boolean[26];
    
    static int max = 0;    // 말이 지날 수 있는 칸 
    
    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());
        
        board = new int[R][C];
        
        for(int i = 0 ; i < R ; i++) {
            char[] ch = br.readLine().toCharArray();
            for(int j = 0 ; j < C ; j++) {
                board[i][j] = ch[j] - 'A';
            }
        }
        
        alphabet[board[0][0]] = true;   // (0,0) 위치의 알파벳 방문 처리
        dfs(0,0,1);
        System.out.println(max);
    }
    
    private static void dfs(int x, int y, int cnt) {
        max = Math.max(max, cnt);
        
        for(int d = 0 ; d < 4 ; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            
            if(nx >= 0 && nx < R && ny >= 0 && ny < C) {
                if(!alphabet[board[nx][ny]]) {  // 지금까지 나온 적 없는 알파벳만 탐색
                    alphabet[board[nx][ny]] = true;
                    dfs(nx, ny, cnt + 1);
                    alphabet[board[nx][ny]] = false;
                }
            }
        }
    }
}
 

 

 

 

 

➕ 다른 풀이 방식

BFS를 활용한 풀이

[백준 1987번] 파이썬 - 알파벳

 

---

💦 어려웠던 점

- BFS로 풀어보려다가 안 되어서 다른 풀이를 참고해 제출했다.

- TC가 추가되었는지 다른 dfs 풀이 제출했더니 98%에서 틀렸었다

 

🧐 새로 알게 된 내용

- BFS가 아니라 DFS를 사용한 이유: 모든 경로를 탐색한 후 그 중 가장 길이가 긴 것을 선택해야 하기 때문

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

백준 1987 알파벳 자바

 

[BOJ] 1987 : 알파벳(Java)