[백준 Java] 9328번 열쇠 (구현, BFS)

[Gold I] 열쇠 - 9328

문제 링크

성능 요약

메모리: 320872 KB, 시간: 1328 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색, 구현

문제 설명

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다.

상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.

• '.'는 빈 공간을 나타낸다.
• '*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
• '$'는 상근이가 훔쳐야하는 문서이다.
• 알파벳 대문자는 문을 나타낸다.
• 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.

마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.

상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.

출력

각 테스트 케이스 마다, 상근이가 훔칠 수 있는 문서의 최대 개수를 출력한다.

 

 

 

💡 나의 접근

1. 건물 주변을 빈 공간으로 두르기.

건물 안으로 들어갈 수 있는 입구를 하나하나 찾아서 저장해두고 각각 들어가보는 것이 나는 귀찮게 느껴져서

건물 주변을 빈공간(.)으로 둘러주었다.

그렇게해서 무조건 (0,0)에서 bfs를 들어가게 되면 벽이 아닌 모든 공간들을 다 탐방하게 된다

 

2. 각 대문자 알파벳(문)을 인덱스로 하는 ArrayList의 배열을 가진다. 

각 배열의 값은 Door 객체를 ArrayList로 가지는 리스트가 들어 있다.

각 칸의 의미는 각 인덱스 알파벳 문(door)의 위치이다. 

3번 인덱스는 D문이 존재하는 모든 위치를 ArrayList에 담아 가진다.

이렇게 하게 된 이유는 D문의 열쇠인 d를 찾았을때 이 배열을 통해서 D가 존재하는 모든 위치를 문에서 빈공간으로 만들어주기 위함이다. 

 

3. 문에 대한 키를 찾으면 위 배열을 통해 빈 공간을 만들어준다. (openDoor)

앞서 말했듯이 D문의 열쇠인 d를 찾았을때 위 배열을 통해서 D가 존재하는 모든 위치를 문에서 빈공간으로 만들어 준다.

처음에는 빈공간을 통해 탐색하면서 문을 만나면 그 키를 가지고 있는지 확인하고 키가 있다면 문을 빈 공간으로 으로 코드를 짜려고 했으나 키가 존재하다면 바로 문을 지워주는 식으로 바꾸었다. 

 

 

4. 열쇠를 만나면 visited (방문)배열을 초기화 하여 방문 했던 곳을 다시 방문하게 한다.

중요한 키포인트 인 것 같다. BFS를 통해 벽을 제외한 모든 공간들을 탐방하게 되는데 이 과정에서 열쇠를 만나게 되면 3번에 의해서 문이 빈공간으로 바뀌게 되고 원래 들어가지 못하는 방을 들어갈 수 있게 된다. 그래서 열쇠로 연 문을 방문해야하는데 이때 이미 방문하고 지나친 곳이라면 다시 visited 배열에 의해 방문을 하지 못하게 되므로 방문 배열을 모두 초기화 시켜 재방문 할 수 있도록 한다.

 

💡 코드

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


public class Main {
//	A - 65
//	a =97
	static final char EMPTY = '.';
	static final char WALL = '*';
	static final char DOCS = '$';
	
	static int T; //테스트 케이스 개수 
	static int R;
	static int C;
	
	
	static char[][] map;
	static boolean[][] visited;
	static ArrayList<Door>[] doors;
	static int dir[][] = {{0,1},{1,0},{0,-1},{-1,0}};
	static int docsCnt;
	static Queue<Point> q;
	static StringBuilder sb = new StringBuilder(); 
	
	static class Point{
		int r;
		int c;
		public Point(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
	}
	
	static class Door{
		char door;
		int r;
		int c;

		public Door(char door, int r, int c) {
			super();
			this.door = door;
			this.r = r;
			this.c = c;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		
		for (int t = 0; t < T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			R = Integer.parseInt(st.nextToken());
			C = Integer.parseInt(st.nextToken());
			
			doors = new ArrayList[26];
			for (int i = 0; i <26; i++) {
				doors[i] = new ArrayList<Door>(); 
			}
			
			
			docsCnt = 0;
			visited = new boolean[R+2][C+2];
			map = new char[R+2][C+2]; // 모든 테두리에 빈 공간을 두르기  -> 어디서든 시작해도 됨
			
			
			//지도 입력
			Arrays.fill(map[0], EMPTY);
			for (int i = 1; i < R+1; i++) {
				String str = EMPTY+br.readLine()+EMPTY;
				for (int j = 0; j < C+2; j++) {
					char c =  str.charAt(j);
					map[i][j] = c;
					if('A' <= c && c <= 'Z') {
						doors[c - 65].add(new Door(c, i, j));
					}
				}
			}
			Arrays.fill(map[R+1], EMPTY);
			
			
			//열쇠 입력
			String keys = br.readLine();
			if(keys.charAt(0) !=  '0') {
				for (int i = 0; i < keys.length(); i++) {
					int k = keys.charAt(i) - 97;
					openDoor(k, map);
					
				}
			}
			

			
			q = new LinkedList<>();
			// 0,0 에서 시작해서 사방으로 나감 
			q.add(new Point(0, 0));
			visited[0][0] = true;
			
			while (!q.isEmpty()) {
				
				Point p = q.poll();
				
	
				if('A' <= map[p.r][p.c]  && map[p.r][p.c] <= 'Z') { 
					//도착한 곳이 문이라면 넘어가기
					continue;
					
					
				} else if(map[p.r][p.c] == DOCS) {
					//보고 있는 곳이 문서라면 docsCnt 증가 후 빈공간으로 바꾸기
					docsCnt++;
					map[p.r][p.c] = EMPTY;
					
					
				}else if('a' <= map[p.r][p.c] && map[p.r][p.c]  <= 'z') {
					// 보고 있는 곳이 열쇠라면 hasKey에 표시 후 빈공간으로 바꾸기
					
					openDoor(map[p.r][p.c] - 97, map); // 그 열쇠로 열 수 있는 모든 문 빈 공간으로 바꾸기 
					map[p.r][p.c]  = EMPTY;
					
					// map 의 방문 배열 초기화 하기 
					visited = new boolean[R+2][C+2];
					
				}
				
				
				
				
				
				for (int d = 0; d < dir.length; d++) {
					int nr = p.r + dir[d][0];
					int nc = p.c + dir[d][1];
					
					if(isInRange(nr, nc) && !visited[nr][nc]) { //범위안에 있고 방문하지 않았다면
						visited[nr][nc] = true;
						
						//벽이 아니라면 나중에 이동할거야 
						if(map[nr][nc] != WALL) {
							q.add(new Point(nr, nc));
						}
						
					}
				}	
			}
			
			sb.append(docsCnt).append("\n");
		}
		System.out.println(sb.toString());
	}
	
	
	
	private static boolean isInRange(int nr, int nc) {
		return nr>=0 && nr < R+2 && nc >= 0 && nc < C+2;
	}



	private static void openDoor(int k, char[][] map) {
		if(doors[k].size() > 0) {
			for (Door d : doors[k]) {
				map[d.r][d.c] = '.';
			}
		}
	}

}