BJ G1 9328 열쇠

BJ G1 9328 열쇠

 

 

문제링크

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

9328번: 열쇠

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

 

동영상 설명

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

https://www.youtube.com/watch?v=Lj1u2byE258

 

 

소스 보기

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

package bj.gold.g1;

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

public class BJ_G1_9328_열쇠 {
    static int T;// 테스트 케이스
    static int H, W;// 지도의 높이와 너비

    static char[][] map;
    static boolean[][][] visited;

    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    // 전체적으로 관리할 열쇠 정보
    static int keyInfo;

    // 구해야 할 정답
    static int maxDocs;

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

        T = Integer.parseInt(input.readLine());
        for (int t = 0; t < T; t++) {
            tokens = new StringTokenizer(input.readLine());
            // 전체를 탐색할 수 있는 '.' 로 둘러버리면 한번에 탐색이 가능하다.
            H = Integer.parseInt(tokens.nextToken()) + 2;
            W = Integer.parseInt(tokens.nextToken()) + 2;

            map = new char[H][W];
            for (char[] row : map) {
                Arrays.fill(row, '.');
            }
            for (int r = 1; r < H - 1; r++) {
                String line = input.readLine();
                for (int c = 1; c < W - 1; c++) {
                    map[r][c] = line.charAt(c - 1);
                }
            }

            keyInfo = 0;

            String keys = input.readLine();
            if (keys.equals("0")) {
                keys = "";
            } else {
                for (int i = 0; i < keys.length(); i++) {
                    update(keys.charAt(i));
                }
            }

            maxDocs = 0;

            bfs(new Point(0, 0));

            System.out.println(maxDocs);
        }
    }

    static void update(char key) {
        keyInfo |= (1 << (key - 'a'));
    }

    static boolean canOpen(char door) {
        return (keyInfo & (1 << door - 'A')) > 0;
    }

    static boolean hasAlready(char key) {
        return (keyInfo & (1 << key - 'a')) > 0;
    }

    static void bfs(Point start) {
        // 닫힌 문에 대한 정보만 별도로 관리하는 List
        List<Point> doorList = new LinkedList<>();

        Queue<Point> q = new LinkedList<>();
        q.offer(start);

        boolean[][] visited = new boolean[H][W];
        visited[start.row][start.col] = true;

        while (!q.isEmpty()) {
            Point front = q.poll();

            if (map[front.row][front.col] == '$') {
                // map[front.row][front.col] = '.'; // 방문 처리 되었으므로 불필요
                maxDocs++;
            }
            for (int d = 0; d < dirs.length; d++) {
                int nr = front.row + dirs[d][0];
                int nc = front.col + dirs[d][1];

                // 해당 지점이 범위 내에 있고 아직 keys 상태에서 미방문이고 벽이 아닌 경우
                if (isIn(nr, nc) && !visited[nr][nc] && map[nr][nc] != '*') {

                    // 문인데 key가 없는 경우는 doorList에 추가해 놓고 나가기.
                    if (map[nr][nc] >= 'A' && map[nr][nc] <= 'Z' && !canOpen(map[nr][nc])) {
                        doorList.add(new Point(nr, nc));
                        continue;
                    }
                    // 키라면
                    else if (map[nr][nc] >= 'a' && map[nr][nc] <= 'z') {
                        // 없던 키라면. 업데이트 하고 block되어있던 것들 다 넣어주자.
                        if (!hasAlready(map[nr][nc])) {
                            update(map[nr][nc]);

                            // 기존에는 가지 못했지만 새로운 키로 열수 있는 문이 생겼다면 그 문을 제거하고 거기서 다시 탐색 시작
                            for (int i = 0; i < doorList.size(); i++) {
                                Point door = doorList.get(i);
                                // A: 65, a: 97, 따라서 둘의 차이는 32
                                if (map[door.row][door.col] == (map[nr][nc] - 32)) {
                                    q.offer(door);
                                    doorList.remove(door);
                                    i--;
                                }
                            }
                        }
                    }
                    visited[nr][nc] = true;
                    Point newThief = new Point(nr, nc);
                    q.offer(newThief);
                }
            }
        }
    }

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

    static class Point {
        int row, col;

        public Point(int row, int col) {
            this.row = row;
            this.col = col;
        }

        @Override
        public String toString() {
            return "Thief [row=" + row + ", col=" + col + "]";
        }
    }

    static String src = "3\r\n" +
                        "5 17\r\n" +
                        "*****************\r\n" +
                        ".............**$*\r\n" +
                        "*B*A*P*C**X*Y*.X.\r\n" +
                        "*y*x*a*p**$*$**$*\r\n" +
                        "*****************\r\n" +
                        "cz\r\n" +
                        "5 11\r\n" +
                        "*.*********\r\n" +
                        "*...*...*x*\r\n" +
                        "*X*.*.*.*.*\r\n" +
                        "*$*...*...*\r\n" +
                        "***********\r\n" +
                        "0\r\n" +
                        "7 7\r\n" +
                        "*ABCDE*\r\n" +
                        "X.....F\r\n" +
                        "W.$$$.G\r\n" +
                        "V.$$$.H\r\n" +
                        "U.$$$.J\r\n" +
                        "T.....K\r\n" +
                        "*SQPML*\r\n" +
                        "irony";
}