BJ G1 1194 달이 차오른다 가자

BJ G1 1194 달이 차오른다 가자

 

 

문제링크

http://www.acmicpc.net/problem/1194

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

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

youtu.be/x6W1d4jU8es

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.g1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * @author itsmeyjc
 * @since 2020. 3. 18.
 * @see https://www.acmicpc.net/problem/1194
 * @mem 15516
 * @time 104
 */
public class BJ_G1_1194_달이차오른다가자 {
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

    static int R, C;

    static char[][] map;
    // 구해야 할 정답
    static int MinMoveCnt;

    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        input = new BufferedReader(new StringReader(src));

        StringTokenizer tokens = new StringTokenizer(input.readLine());
        R = Integer.parseInt(tokens.nextToken());
        C = Integer.parseInt(tokens.nextToken());

        map = new char[R][C];

        Minsik start = null;
        for (int r = 0; r < R; r++) {
            map[r] = input.readLine().toCharArray();
            for (int c = 0; c < C; c++) {
                if (map[r][c] == '0') {
                    start = new Minsik(r, c, 0, 0);
                }
            }
        }

        /*        System.out.println("입력 확인");
        for (char[] row : map) {
            System.out.println(Arrays.toString(row));
        }
        System.out.println("민식: " + start);*/

        MinMoveCnt = Integer.MAX_VALUE;

        bfs(start);

        System.out.println(MinMoveCnt == Integer.MAX_VALUE ? -1 : MinMoveCnt);
    }

    static void bfs(Minsik start) {
        Queue<Minsik> q = new LinkedList<>();
        q.offer(start);
        // 키의 최대 개수는 6개이고 이것들이 각각 있고 없고의 상태가 달라진다.
        // 따라서 세번째로 관리해야 할 요소들의 모드 키 관련 부분집합의 개수가 된다.
        boolean[][][] visited = new boolean[R][C][1 << 6];

        visited[start.row][start.col][start.keys] = true;

        while (!q.isEmpty()) {
            Minsik front = q.poll();
            // 이 지점이 '1'이면 그만~
            if (map[front.row][front.col] == '1') {
                MinMoveCnt = front.depth;
                return;
            }

            for (int d = 0; d < dirs.length; d++) {
                int nr = front.row + dirs[d][0];
                int nc = front.col + dirs[d][1];

                // 해당 좌표를 현재의 키 상태로 방문한 적이 없다면.
                if (isIn(nr, nc) && !visited[nr][nc][front.keys]) {
                    // 벽이면 이동 불가
                    if (map[nr][nc] == '#') {
                        continue;
                    }

                    // 문을 만났는데 키가 없으면 못감
                    if (map[nr][nc] >= 'A' && map[nr][nc] <= 'Z' && !front.hasKey(map[nr][nc])) {
                        continue;
                    }

                    // 아니면 갈 수 있음: 방문 처리 및 새로운 민식이의 탄생!!
                    visited[nr][nc][front.keys] = true;
                    Minsik newMinsik = new Minsik(nr, nc, front.depth + 1, front.keys);

                    // 혹시 키를 만나면 키 정보 업데이트
                    if (map[nr][nc] >= 'a' && map[nr][nc] <= 'z') {
                        newMinsik.updateKey(map[nr][nc]);
                    }

                    // 다음 방문
                    q.offer(newMinsik);
                }
            }
        }
    }

    static boolean isIn(int row, int col) {
        return 0 <= row && row < R && 0 <= col && col < C;
    }

    static class Minsik {
        int row, col, depth;
        int keys;// 키 보유 상태

        public Minsik(int row, int col, int depth, int keys) {
            this.row = row;
            this.col = col;
            this.depth = depth;
            this.keys = keys;
        }

        // 민식이의 키 상태를 업데이트 한다.
        public void updateKey(char key) {
            keys |= (1 << key - 'a');
        }

        // 민식이가 이 키를 가지고 있는지 반환한다.
        public boolean hasKey(char key) {
            return (keys & 1 << key - 'A') > 0;
        }
    }

    private static String src = "7 8\r\n" +
                                "a#c#eF.1\r\n" +
                                ".#.#.#..\r\n" +
                                ".#B#D###\r\n" +
                                "0....F.1\r\n" +
                                "C#E#A###\r\n" +
                                ".#.#.#..\r\n" +
                                "d#f#bF.1";
}