[백준]1987: 알파벳 - JAVA

[백준]1987: 알파벳

www.acmicpc.net/problem/1987

1987번: 알파벳

풀이

백트랙킹 + DFS문제이다.

이전에 알파벳을 뽑았는지 확인하기 위해 알파벳의 개수만큼의 크기의 배열을 boolean타입으로 만들어주었다. 

그리고 dfs탐색을 하면서 이전에 뽑은 알파벳이 아닌 경우에 탐색을 진행하도록 하였다.

 

알파벳을 처리하는 방법 즉, boolean배열로 방문 노드를 표시하듯이 알파벳을 처리해주는 아이디어만 생각해 낸다면 이후로는 기존의 dfs탐색 풀이와 똑같다.

 

코드

import java.util.*;
 
public class Main {    
 
    static int r, c;
    static int[][] board;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int max = 0;
    static boolean[] alpha;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        r = scan.nextInt();
        c = scan.nextInt();
        scan.nextLine();
        
        //board를 입력받는다.
        board = new int[r][c];
        for(int i = 0; i < r; i++) {
            String str = scan.nextLine();
            for(int j = 0; j < c; j++) {
                board[i][j] = str.charAt(j) - 'A';
            }
        }
        
        alpha = new boolean[26]; //알파벳을 이전에 방문했는지 여부 체크.
        backtracking(0, 0, 1);
        System.out.println(max);
    }
    
    public static void backtracking(int x, int y, int len) {
        alpha[board[x][y]] = true; 
        max = Math.max(max, len);
        
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 0 && ny >= 0 && nx < r && ny < c) {
                if(alpha[board[nx][ny]] == false) {
                    backtracking(nx, ny, len + 1);
                    alpha[board[nx][ny]] = false;
                }
            }
        }
    }
}