[BOJ/Java] 1194. 달이 차오른다, 가자.

[BOJ/Java] 1194. 달이 차오른다, 가자.

 

1194번: 달이 차오른다, 가자.

---

풀이

import java.io.*;
import java.util.*;

public class Main {
    char[][] graph; // 미로의 정보를 담는 2차원 배열
    int n, m; // 미로의 세로, 가로 크기
    int[][] direction = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } }; // 상하좌우 이동을 위한 방향 배열

    public static void main(String[] args) throws IOException {
        new Main().io(); // Main 클래스의 io 메서드 호출
    }

    private void io() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader 생성
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // 출력을 위한 BufferedWriter 생성
        StringBuilder sb = new StringBuilder(); // 출력을 위한 StringBuilder 생성
        StringTokenizer st = new StringTokenizer(br.readLine()); // 입력 받은 문자열을 공백 기준으로 나누기 위한 StringTokenizer 생성

        n = Integer.parseInt(st.nextToken()); // 미로의 세로 크기 입력 받음
        m = Integer.parseInt(st.nextToken()); // 미로의 가로 크기 입력 받음

        graph = new char[n][m]; // 미로의 정보를 저장하기 위한 2차원 배열 초기화

        int startX = 0, startY = 0; // 민식이의 시작 위치 초기화
        for (int x = 0; x < n; x++) {
            String s = br.readLine(); // 한 줄씩 미로 정보 입력 받음
            for (int y = 0; y < m; y++) {
                graph[x][y] = s.charAt(y); // 미로의 정보를 2차원 배열에 저장
                if (graph[x][y] == '0') { // 민식이의 시작 위치 찾기
                    startX = x;
                    startY = y;
                }
            }
        }

        // 미로를 탈출하는데 필요한 최소 이동 횟수 계산
        int ans = sol(startX, startY, 0, new boolean[n][m][64], 0);
        sb.append(ans); // 결과 문자열에 추가

        bw.write(sb.toString()); // 결과 출력
        bw.flush();
        bw.close(); // BufferedWriter 닫기
    }

    // 미로를 탈출하는데 필요한 최소 이동 횟수 계산하는 메서드
    private int sol(int x, int y, int cnt, boolean[][][] visited, int keys) {

        Queue<Point> queue = new ArrayDeque<>(); // BFS를 위한 큐 생성
        visited[x][y][keys] = true; // 시작 위치 방문 처리
        queue.offer(new Point(x, y, cnt, visited, keys)); // 시작 위치 큐에 추가

        while (!queue.isEmpty()) { // 큐가 빌 때까지 반복
            Point p = queue.poll(); // 큐에서 하나의 위치 정보 가져옴
            x = p.x;
            y = p.y;
            cnt = p.cnt;
            visited = p.visited;
            keys = p.keys;

            for (int d = 0; d < direction.length; d++) { // 상하좌우 이동을 위한 반복문
                int newX = x + direction[d][0]; // 새로운 x 좌표 계산
                int newY = y + direction[d][1]; // 새로운 y 좌표 계산
                if (checkStatus(newX, newY, visited, keys)) { // 이동 가능한지 확인
                    if (checkGo(newX, newY)) { // 일반 길인 경우
                        visited[newX][newY][keys] = true; // 해당 위치 방문 처리
                        queue.offer(new Point(newX, newY, cnt + 1, visited, keys)); // 큐에 추가
                    } else if (checkAns(newX, newY)) { // 탈출 위치인 경우
                        return cnt + 1; // 이동 횟수 반환
                    } else if (checkKey(newX, newY)) { // 열쇠를 찾은 경우
                        int newKey = 1 << (graph[newX][newY] - 'a'); // 새로운 열쇠 계산
                        newKey |= keys; // 기존의 열쇠와 합침
                        visited[newX][newY][newKey] = true; // 해당 위치 방문 처리
                        queue.offer(new Point(newX, newY, cnt + 1, visited, newKey)); // 큐에 추가
                    } else if (checkDoor(newX, newY)) { // 문인 경우
                        if (haveKey(newX, newY, keys)) { // 해당 문의 열쇠를 가지고 있는지 확인
                            visited[newX][newY][keys] = true; // 열쇠가 있으면 해당 위치 방문 처리
                            queue.offer(new Point(newX, newY, cnt + 1, visited, keys)); // 큐에 추가
                        }
                    }
                }
            }
        }

        return -1; // 미로를 탈출할 수 없는 경우 -1 반환
    }

    // 이동 가능한지 확인하는 메서드
    private boolean checkStatus(int x, int y, boolean[][][] visited, int keys) {
        return 0 <= x && x < n && 0 <= y && y < m && graph[x][y] != '#' && !visited[x][y][keys];
    }

    // 일반 길인지 확인하는 메서드
    private boolean checkGo(int x, int y) {
        return graph[x][y] == '.' || graph[x][y] == '0';
    }

    // 탈출 위치인지 확인하는 메서드
    private boolean checkAns(int x, int y) {
        return graph[x][y] == '1';
    }

    // 열쇠를 찾은 경우인지 확인하는 메서드
    private boolean checkKey(int x, int y) {
        return graph[x][y] >= 'a' && graph[x][y] <= 'f';
    }

    // 문인지 확인하는 메서드
    private boolean checkDoor(int x, int y) {
        return graph[x][y] >= 'A' && graph[x][y] <= 'F';
    }
    
    // 해당 문의 열쇠를 가지고 있는지 확인하는 메서드
    private boolean haveKey(int x, int y, int keys) {
        return (keys & (1 << graph[x][y] - 'A')) != 0;
    }

    // 위치 정보를 담는 클래스
    class Point {
        int x;
        int y;
        int cnt; // 현재까지의 이동 횟수
        boolean[][][] visited; // 방문 여부
        int keys; // 현재 가지고 있는 열쇠

        // 생성자
        public Point(int x, int y, int cnt, boolean[][][] visited, int keys) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
            this.visited = visited;
            this.keys = keys;
        }
    }
}