[BOJ] 백준 [9328] 열쇠 JAVA

문제

풀이

 

이 문제에서 집어야 할 포인트는 세 가지다.

 

1. 3차원 visit[][][] 배열을 사용하여 열쇠를 먹을때 마다 visit[][][index++] 을 처리해줘서 열쇠 먹은시점이랑 열쇠를 안 먹은 시점이랑 분리 시키는 것.

 

2. BFS를 위해 집어 넣을 노드인 'Point' 에 대해 Comparable을 구현하여 열쇠를 가장 많이 먹은 시점이 우선 탐색할 수 있도록 해주는것.

 

3. 우선순위 큐인 PriorityQueue<Point>를 사용할 것. 

 

 

import java.util.*;
import java.io.*;
 
public class Main{
    static int TC;
    public static int w,h; // 너비 , 높이
    public static int[][] map; 
    public static boolean[] hasKey; // 열쇠를 가지고 있는지에 대한 여부
    public static boolean[][][] visit;
    public static int[] dx = {1,-1,0,0};
    public static int[] dy = {0,0,1,-1};
 
    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //테스트 케이스
        TC = Integer.parseInt(br.readLine());
        while (TC-->0){
            String[] input = br.readLine().split(" ");
            w = Integer.parseInt(input[1]);
            h = Integer.parseInt(input[0]);
 
            map = new int[h+2][w+2];
            visit = new boolean[h+2][w+2]['z'-'a'+2];
            hasKey = new boolean['z'+1];
 
            //외벽 생성
            for(int i=0;i<=h+1;i++)
                Arrays.fill(map[i],'.');
 
            //map 생성
            for(int i=1;i<=h;i++){
                char[] chars = br.readLine().toCharArray();
                for(int j=0;j<chars.length;j++){
                    map[i][j+1] = chars[j];
                }
            }
 
            //미리 주어진 key 생성
            String key = br.readLine();
            int keyCnt=0;
            if(!key.equals("0")) {
                char[] keys = key.toCharArray();
                keyCnt = keys.length;
                for (char c : keys) hasKey[c] = true;
            }
 
            //열쇠를 먹을 수록 새로운 경로를 만들 수 있으니, 열쇠 갯수에 따라 우선순위 결정
            Queue<Point> q = new PriorityQueue<Point>();
            q.add(new Point(0,0,keyCnt));
 
            int answer=0;//문서의 갯수
 
            while(!q.isEmpty()){
                Point tmp = q.poll();
                int curKey = tmp.keyCnt;
 
                //시간복잡도를 조금이라도 줄이기위한것 (이미 모든 곳을 탐색했다면, 더 이상 탐색 할 필요가 없다)
                if(curKey < keyCnt)
                    break;
                visit[tmp.y][tmp.x][curKey] = true;
 
                for(int i=0;i<dx.length;i++){
                    int nextX = tmp.x+dx[i];
                    int nextY = tmp.y+dy[i];
 
                    //범위를 벗어나거나 , 이미 방문한 지점이거나 벽이면 PASS
                    if(!isRange(nextX,nextY) || visit[nextY][nextX][curKey] || map[nextY][nextX]=='*')
                        continue;
 
                    //그냥 지나갈 수 있는 경로면
                    if(map[nextY][nextX] == '.')
                        q.add(new Point(nextX,nextY,curKey));
                    //그 지점의 열쇠를 이미 획득 했다면
                    else if(hasKey[map[nextY][nextX]]){
                        map[nextY][nextX] = '.';
                        q.add(new Point(nextX,nextY,curKey));
                    }
                    // 처음 먹어보는 열쇠가 있다면 새로운 visit배열을 탐색하도록 curKey값을 올려준 Point를 큐에 삽입
                    else if(map[nextY][nextX] >='a' && map[nextY][nextX] <='z' && !hasKey[map[nextY][nextX]]){
                        hasKey[map[nextY][nextX]] = true;
                        map[nextY][nextX] = '.';
                        curKey++;
                        keyCnt++; // 시간복잡도를 조금이라도 줄이기 위한 변수
                        q.add(new Point(nextX,nextY,curKey));
                    }
                    // 문을 마주쳤을때
                    else if(map[nextY][nextX] >='A' && map[nextY][nextX] <='Z'){
                        char door = (char)map[nextY][nextX];
                        char needKey = Character.toLowerCase(door);
                        //그 지점의 열쇠를 가지고 있다면
                        if(hasKey[needKey]){
                            map[nextY][nextX] = '.';
                            q.add(new Point(nextX,nextY,curKey));
                        }
                    }
                    // 문서가 있다면
                    else if(map[nextY][nextX] == '$'){
                        answer++;
                        map[nextY][nextX] = '.';
                        q.add(new Point(nextX,nextY,curKey));
                    }
                }
 
            }
            //정답 출력
            System.out.println(answer);
        }
    }
    static Boolean isRange(int x,int y){
        return x>=0&&x<=w+1 && y>=0&&y<=h+1;
    }
 
}
class Point implements Comparable<Point>{
    int x;
    int y;
    int keyCnt;
 
    public Point(int x, int y,int keyCnt) {
        this.x = x;
        this.y = y;
        this.keyCnt=keyCnt;
    }
 
    @Override
    public int compareTo(Point o) {
        return o.keyCnt-this.keyCnt;
    }
}
 
 
 
 
 
 

 

 

두 번의 시도간의 시간복잡도가 차이가 나는이유는 다음과 같다.

KeyCnt 라는 변수를 만들어줘서 우선순위큐에 열쇠를 가장 많이 시점보다 적은 key를 가진 노드 Point가 나온다면

큐 탐색를 종료한다. (이유 : 이미 그 시점이 왔다면 모든 곳을 탐색을 완료 하였기 때문에)

 

조금 복잡하긴 했지만 천천히 경우를 따져가면서 한다면 쉽게할 수 있는 문제였다.