[백준] 알고리즘 분류(그래프 이론,JAVA)9328번, 열쇠

문제 링크

9328번: 열쇠

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 상근이는 상하좌우 이동이 가능하며, 빌딩 안팎을 드나들 수 있습니다.

2. 빌딩의 문과 열쇠는 알파벳으로 표현하며, 열쇠는 바닥에 놓여있습니다.

3. 열쇠는 여러번 사용할 수 있습니다.

4. '$'으로 표현된 문서를 훔칠 수 있는 최대 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. BFS를 반복하여 열쇠를 사용하는 경우를 탐색합니다.

 

3. 탐색이 끝났을 때 문서를 훔치는 최대 개수를 결과로 출력합니다.

 

BFS 탐색!

 

BFS를 탐색할 때 문을 방문한 뒤, 열쇠를 먹을 수 있는 경우가 발생할 수 있습니다.

 

해당 경우를 발생하지 않기 위해서 BFS탐색을 빌딩의 문을 더 이상 열지 않을 때까지 반복합니다.

 

1. 빌딩 밖에서 BFS탐색을 진행하여 최대한 열쇠와 문을 열어보고 열지 못한 문을 따로 저장합니다.

 

2. 닫힌 문에서 열쇠를 찾은 문이 없을 때까지 닫힌 문 기준 BFS탐색을 반복합니다.

 

이 과정을 진행되는 것을 예제입력을 통해서 보여드리겠습니다.

 

예제입력 1.

1. 입력된 정보를 저장합니다.

※1번째 테스트케이스의 경우만 보여드리겠습니다.

 

H : 5

W : 17

 

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

.

.

.

.

.

.

.

.

.

.

.

.

.

*

*

$

*

*

B

*

A

*

P

*

C

*

*

X

*

Y

*

.

X

.

*

y

*

x

*

a

*

p

*

*

$

*

$

*

*

$

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

 

얻은 열쇠 : { c, z }

 

2. BFS를 반복하여 열쇠를 사용하는 경우를 탐색합니다.

 

1. 빌딩 밖에서 BFS탐색을 진행하여 최대한 열쇠와 문을 열어보고 열지 못한 문을 따로 저장합니다.

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

.

.

.

.

.

.

.

.

.

.

.

.

.

*

*

$

*

*

B

*

A

*

P

*

C

*

*

X

*

Y

*

.

X

.

*

y

*

x

*

a

*

p

*

*

$

*

$

*

*

$

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

 

얻은 열쇠 : { c, p, z }

 

2. 닫힌 문에서 열쇠를 찾은 문이 없을 때까지 닫힌 문 기준 BFS탐색을 반복합니다.

 

닫힌 문 : { B, A, P, X, Y }

 

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

.

.

.

.

.

.

.

.

.

.

.

.

.

*

*

$

*

*

B

*

A

*

P

*

C

*

*

X

*

Y

*

.

X

.

*

y

*

x

*

a

*

p

*

*

$

*

$

*

*

$

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

 

닫힌 문 : { B, A, X, Y }

 

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

.

.

.

.

.

.

.

.

.

.

.

.

.

*

*

$

*

*

B

*

A

*

P

*

C

*

*

X

*

Y

*

.

X

.

*

y

*

x

*

a

*

p

*

*

$

*

$

*

*

$

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

 

닫힌 문 : { B, X, Y }

 

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

.

.

.

.

.

.

.

.

.

.

.

.

.

*

*

$

*

*

B

*

A

*

P

*

C

*

*

X

*

Y

*

.

X

.

*

y

*

x

*

a

*

p

*

*

$

*

$

*

*

$

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

 

닫힌 문 : { B, Y }

 

더 이상 열쇠가 없어서 열 수 있는 문은 존재하지 않으므로 탐색 종료!

 

3. 탐색이 끝났을 때 문서를 훔치는 최대 개수를 결과로 출력합니다.

 

훔친 개수 : 3개 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 H, W를 띄어쓰기 기준 나누었습니다.
• 첫 BFS탐색으로 닫힌 문과 열쇠, 문서를 최대한 수집합니다.
• 닫힌 문을 기준으로 열쇠를 소지한 것이 존재하면 BFS탐색을 반복하여 탐색합니다.
• 탐색이 종료되었을 때 훔친 문서의 최대수를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs함수는 빌딩 1층을 BFS탐색을 진행하여 닫힌 문, 열쇠, 문서를 수집합니다.
• inSpace함수는 좌표가 빌딩 안팎에 존재하는지 확인합니다.

 

결과코드

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

public class Main {
    //BFS탐색을 위한 row, col 정보 클래스
    static class Pos{
        int r, c;
        public Pos(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
    //상하좌우 row 변경값
    static int[] dr = {-1, 1, 0, 0};
    //상하좌우 col 변경값
    static int[] dc = {0, 0, -1, 1};
    static int[][] map;		//빌딩 1층 정보 저장 배열
    static boolean[][] visited;	//빌딩 1층 방문 확인 배열
    static boolean[] keys;	//열쇠 소유 확인 배열
    //열리지 않은 닫힌 문 저장 Queue
    static Queue<Pos> locked = new LinkedList<>();
    static int H, W, result;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        //T번 테스트케이스 진행
        for(int tc=0;tc<T;tc++){
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            H = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            result = 0;
            map = new int[H + 2][W + 2];
            visited = new boolean[H+2][W+2];
            keys = new boolean[26];
            locked.clear();
            //빌딩 1층 정보 저장
            for(int i=1;i<=H;i++) {
                String str = br.readLine();
                for (int j = 1; j <= W; j++)
                    map[i][j] = str.charAt(j-1);
            }
            String str = br.readLine();
            //기본 소유한 열쇠 저장
            if(!str.equals("0")){
                for(int i=0;i<str.length();i++){
                    char c = str.charAt(i);
                    keys[c - 97] = true;
                }
            }
            //1. 빌딩 밖에서 BFS탐색을 진행하여 
            //최대한 열쇠와 문을 열어보고 열지 못한 문을 따로 저장합니다.
            bfs(0, 0);

            //2. 닫힌 문에서 열쇠를 찾은 문이 없을 때까지 
            //닫힌 문 기준 BFS탐색을 반복합니다.
            while(true){
                boolean isUpdate = false;
                int size = locked.size();
                //닫힌 문 탐색
                for(int i=0;i<size;i++){
                    Pos cur = locked.poll();
                    //닫힌 문의 열쇠를 가지고 있지 않을 때
                    if(!keys[map[cur.r][cur.c]-65]) {
                        locked.offer(cur);
                        continue;
                    }
                    isUpdate = true;	//닫힌 문을 1번이라도 열었을 때
                    bfs(cur.r, cur.c);	//BFS탐색 진행
                }
                //더 이상 열 수 있는 문이 없을 때
                if(!isUpdate || locked.isEmpty())
                    break;
            }
            System.out.println(result);	//최대 문서 개수 출력
        }
    }
    //빌딩 1층을 BFS탐색하는 함수
    static void bfs(int r, int c){
        Queue<Pos> q = new ArrayDeque<>();
        q.add(new Pos(r, c));
        visited[r][c] = true;
        //BFS탐색 진행
        while(!q.isEmpty()){
            Pos cur = q.poll();
            //상하좌우 이동하며 인접 탐색
            for(int i=0;i<4;i++){
                int tempR = cur.r + dr[i];
                int tempC = cur.c + dc[i];
                if(inSpace(tempR,tempC) && !visited[tempR][tempC] && map[tempR][tempC] != 42) {
                    visited[tempR][tempC] = true;
                    //열쇠일 때
                    if (map[tempR][tempC] >= 97) {
                        keys[map[tempR][tempC] - 97] = true;
                        q.add(new Pos(tempR, tempC));
                    }else if (map[tempR][tempC] >= 65) {	//닫힌 문일 때
                        if (keys[map[tempR][tempC] - 65])	//해당 열쇠 소유
                            q.add(new Pos(tempR, tempC));
                        else	//해당 열쇠 미소유
                            locked.add(new Pos(tempR, tempC));
                    } else {	//열쇠와 닫힌 문과 벽이 아닐 때
                        if (map[tempR][tempC] == 36)	//훔칠 문서일 때
                            result++;
                        q.offer(new Pos(tempR, tempC));
                    }
                }
            }
        }
    }
    //빌딩 안밖에 존재하는지 확인하는 함수
    static boolean inSpace(int r, int c){
        if(r >= 0 && c >= 0 && r <=H+1 && c <= W+1)
            return true;
        return false;
    }
}