[ 백준 - Java ] 알파벳 ( 자바 )

( dfs / 알파벳 / 1987 )

[문제]

문제 설명

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

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

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

제한사항

메모리 제한 : 256 MB

입출력 예시

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

 

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

---

[코드]

import java.util.Scanner;

class Alphabet1987 {
    static int answer;      // 이동 거리
    static int h;           // 높이
    static int w;           // 너비
    static int[][] map;     // 지도 정보
    // A ~ Z 까지 0 ~ 25로 표현
    static boolean[] alpha = new boolean[26];
    // x, y좌표 이동시 이동할 크기
    static final int[] dx = {0, 1, 0, -1};
    static final int[] dy = {-1, 0, 1, 0};

    public static void main(String[] args){
        // === 입력 ===
        Scanner sc = new Scanner(System.in);
        // 세로, 가로 크기 문자열로 입력 후 공백으로 나눔
        String[] tmp = sc.nextLine().split(" ");
        // 문자열로 되있는 세로와 가로를 정수로 변환
        h = Integer.parseInt(tmp[0]);
        w = Integer.parseInt(tmp[1]);
        // 입력받은 크기에 맞도록 초기화
        map = new int[h][w];
        // 지도정보 입력
        for(int i = 0; i < h; i++){
            String mapInfo = sc.nextLine();             // 행을 문자열로 입력받음

            for(int j = 0; j < w; j++){
                map[i][j] = mapInfo.charAt(j) - 'A';    // 문자로 하나씩 접근하며 알바펫을 0 ~ 25 숫자로 변환
            }
        }
        sc.close();

        // === 풀이 ===
        answer = 1;                 // 최소 크기가 1임으로 1로 정답 초기화
        dfs(0, 0, 0);   // 0, 0 위치부터 깊이 우선 탐색

        // === 출력 ===
        System.out.println(answer);
    }

    // 깊이 우선 탐색
    public static void dfs(int x, int y, int cnt){
        // 이미 방문했던 알파벳일 경우
        if(alpha[map[y][x]]) {
            // 지금까지 카운트한 cnt와 answer 비교해서 큰 값 저장
            answer = Math.max(answer, cnt);
            return;     // 깊이 우선 탐색 종료
        }
        // 현재 위치 방문처리
        alpha[map[y][x]] = true;
        // 4방향 모두 탐색 시도
        for(int i = 0; i < 4; i++){
            // 다음 위치 계산
            int nx = x + dx[i];
            int ny = y + dy[i];
            // 범위내 다음 위치가 있을 경우
            if(nx >= 0 && nx < w && ny >= 0 && ny < h){
                // 카운트 증가하면서 다음 위치로 깊이 우선 탐색
                dfs(nx, ny, cnt + 1);
            }
        }
        // 다시 다른 방향 탐색을 위해 방문처리 해제 (백트래킹)
        alpha[map[y][x]] = false;
    }
}

문제 링크

1987번: 알파벳

제가 잘못 알고 있거나 잘못된 부분이 있을 경우 알려주시고 추가로 궁금한 점 있으신 분들도 댓글이나 메일 주시면 성실히 답변해 드리겠습니다.🧑🏻‍💻

감사합니다~😄