[백준] 1987 알파벳 (JAVA)

문제 링크:

1987번: 알파벳

 

 

난이도: 골드 4

 

 

문제:

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

 

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

 

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

 

 

입력:

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.'

 

 

출력:

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

 

 

문제 이해:

이 문제는 이해하기 어렵지 않다. 시작점 (0,0)에서 출발하여 상·하·좌·우로 이동하면서, 처음 만나는 알파벳이라면 앞으로 나아가고, 이미 사용한 알파벳이라면 이동하지 못한다. 이렇게 해서 이동할 수 있는 가장 긴 경로의 길이를 구하는 것이다.

예제 입력 1을 살펴보자.

2 4
CAAB
ADCB

 

시작점은 C이고, 이후 같은 알파벳을 두 번 거치지 않으면서 가장 멀리 이동할 수 있는 경로는
C → A → D 이므로, 정답은 3이 된다.

 

 

구현 방향:

작성자는 처음에 BFS 방식으로 탐색하여 큐에 사용한 알파벳들을 저장해 두고 가장 긴 경로를 구하려 했다. 그러나 이 경우 큐에 X좌표, Y좌표, 경로 정보까지 모두 담아야 하므로 구현이 복잡해졌다.

 

따라서 DFS 방식으로 전환하였다. DFS 탐색을 통해 아직 사용하지 않은 알파벳을 방문하면서 경로를 확장하고, 더 이상 이동할 곳이 없으면 백트래킹을 통해 한 단계 뒤로 돌아가 방문 여부를 해제한다. 이런 과정을 반복하여 결과적으로 가장 긴 경로를 찾을 수 있었다.

 

이를 그대로 코드로 구현하면 다음과 같다.

 

 

정답코드:

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 {
    static int R,C;
    static char [][]matrix;
    static boolean[][]visited;
    static int max=Integer.MIN_VALUE;
    static int []dx={-1,1,0,0};
    static int []dy={0,0,-1,1};
    static boolean [] usedAlphabet=new boolean[26];

    public static void dfs(int x, int y, int depth){
        max=Math.max(max,depth);

        //상하좌우 탐색
        for(int d=0; d<4; d++){
            int nx= x+dx[d];
            int ny= y+dy[d];

            if(nx<0 || ny<0 || nx>=R || ny>=C) continue;

            int c = matrix[nx][ny] - 'A';
            if (!usedAlphabet[c]) {
                usedAlphabet[c] = true;
                dfs(nx, ny, depth+1);
                usedAlphabet[c] = false; // 백트래킹
            }

        }

    }

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

        matrix=new char[R][C];
        visited=new boolean[R][C];

        for (int i=0; i<R; i++){
            StringBuilder sb=new StringBuilder(br.readLine());
            for (int j=0; j<C; j++){
                matrix[i][j]=sb.charAt(j);
            }
        }

        //초기 세팅 끝

        //탐색 시작
        usedAlphabet[matrix[0][0]-'A'] = true; //시작점은 방문 표시
        dfs(0, 0,1);

        //결과 출력
        System.out.println(max);


    }
}

 

 

감사합니다.