백준 9328번 : 열쇠 [자바]

 

🧫 문제 분석

 

✔️ 출처

열쇠 골드 1

 

📖 문제

 

BFS 탐색 + 구현

 

상근이가 빈 공간을 다니면서 문서를 훔친다.

열쇠는 줍고 열쇠가 있는 문이라면 연다.

 

 

처음풀이시도에서는

열쇠를 얻자마자 해당하는 문에 이동하고

그 문의 상하좌우를 탐색해서 한번이라도 방문한 빈 공간이 있다면 이 문은 

이동 가능한 문으로 판단하여 탐색했는데 

 

이 풀이의 문제점은 

문의 상하좌우의 빈 공간이 방문이 가능함에도 

열쇠를 얻은 시점이 더 빨라서 

해당 열쇠가 있음에도 이동 할 수 없는 문이라 판단하여  열지 않는다.

 

 

따라서 우선 빈 공간을 먼저 다 탐색하면서

갖고 있는 열쇠가 있다면 문을 열고 

열 수 없는 문은 따로 저장해두고

새로운 열쇠는 추가한다. 

 

기존에 갖고 있는 열쇠로 다 탐색을 끝냈다면

추가된 키로 열 수 있는 문이 있는지 확인후 

열 수 있다면 열고 탐색하기 위해 큐에 추가한다.

 

---

🔅 문제 풀이

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

public class Main {
    static int r, c;
    static int[] dy = {1, -1, 0, 0};
    static int[] dx = {0, 0, 1, -1};

    static char[][] map; // 맵
    static boolean[][] visited; // 방문 처리
    static List<int[]>[] doorList; // 문 리스트
    static Set<Character> ownKeySet; // 가지고 있는 키

    // 0. 0,0 부터 BFS 탐색 시작
    // 1. bfs 탐색하면서 가지고있던 키로 문열기
    // 1-1. 못여는 문이라면 문 리스트에 저장 
    // 2. 얻은 키는 ownKey에 저장 
    // 3. 1번 탐색이 끝났다면  갖고 있는 키로 열 수 있는 문이 있으면 탐색하기위 해 큐에 저장하고 1번부터 다시 시작 
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            r = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            map = new char[r + 2][c + 2];
            visited = new boolean[r + 2][c + 2];
            doorList = new List['Z' - 'A' + 1];
            ownKeySet = new HashSet<>();

            for (int i = 0; i < doorList.length; i++) {
                doorList[i] = new ArrayList<>();
            }

            // 빈 공간 채우기
            for (int i = 0; i < r+2; i++) {
                Arrays.fill(map[i], '.');
            }

            // 맵 입력
            for (int i = 1; i < r + 1; i++) {
                char[] ch = br.readLine().toCharArray();
                for (int j = 1; j < c + 1; j++) {
                    map[i][j] = ch[j - 1];
                }
            }

            // 키 입력
            for (char key : br.readLine().toCharArray()) {
                if (key == '0') break;
                ownKeySet.add(key);
            }
            
            sb.append(bfs()).append("\n");
        }

        System.out.print(sb.toString());
    }



    private static int bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0});
        visited[0][0] = true;

        int cnt = 0;

        while (!q.isEmpty()) {
            int[] cur = q.poll();

            for (int i = 0; i < 4; i++) {
                int nextR = cur[0] + dy[i];
                int nextC = cur[1] + dx[i];

                if (nextR < 0 || nextR >= map.length
                        || nextC < 0 || nextC >= map[0].length
                        || visited[nextR][nextC] || map[nextR][nextC] == '*') continue;

                // 문이라면
                if ('A' <= map[nextR][nextC] && map[nextR][nextC] <= 'Z') {
                    char key = (char)(map[nextR][nextC] + 32);
                    int ch = map[nextR][nextC] - 'A';

                    // 키가 없다면 문 리스트에 저장
                    if (!ownKeySet.contains(key)) {
                        doorList[ch].add(new int[]{nextR, nextC});
                        continue; // 키가 없다면 넘어감
                    }


                    // 키라면
                } else if ('a' <= map[nextR][nextC] && map[nextR][nextC] <= 'z') {
                    ownKeySet.add(map[nextR][nextC]);

                    // 문서면 훔친다.
                } else if (map[nextR][nextC] == '$') {
                    cnt++;
                }

                map[nextR][nextC] = '.';
                visited[nextR][nextC] = true;
                q.add(new int[]{nextR, nextC});
            }


            // 얻은 새로운 키들로 탐색
            if (q.isEmpty()) {
                for (char key : ownKeySet) {
                    int idx = key - 'a';
                    
                    if (doorList[idx].isEmpty()) continue;

                    for (int[] pos : doorList[idx]) {
                        int r = pos[0];
                        int c = pos[1];

                        // 문을 방문하지 않았다면 큐에 저장 
                        if(!visited[r][c]) {
                            map[r][c] = '.';
                            visited[r][c] = true;
                            q.add(new int[]{r, c});
                        }
                    }
                }
            }

        }

        return cnt;

    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1.  밖에서 접근 가능할때는 맵을 한칸 더 크게 만드는 법을 배웠다. 
   1. r + 2 c + 2