[백준 9328] 열쇠 / 자바 / bfs + 구현

#문제         

레벨: G1
알고리즘: bfs + 구현
풀이시간: 1시간 
힌트 참조 유무: 유

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

---

#문제 풀이        

이 문제에서 중요한 건 bfs가 아니다. 구현에 초점에 맞춰진 문제이다. 그냥 bfs로 탐색하면 지금은 못가더라도 나중에 키(소문자)를 획득하고 나서 갈 수 있는 곳은 어떻게 갈 것인가? 어떻게 구현할 것인가를 묻고 있다. 

아이디어는 간단하다. 지금 열 수 없는 문은 나중에 열 수도 있으니 저장해둔다. 그리고 해당 키를 얻었을 때 열 수 있는 문을 다 열고 마저 탐색한다.

나머지는 주석참고 바란다.

---

#풀이 코드      

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

public class Main {
	public static int n, m;
	public static char[][] map;
	public static int max_cnt;
	public static boolean[][] visited;
	public static boolean[] key;
	public static ArrayList<Node>[] door;
	public static class Node {
		int x;
		int y;
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	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));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		int TC = Integer.parseInt(br.readLine());
		for(int test_case=1;test_case<=TC;test_case++) {
			st = new StringTokenizer(br.readLine(), " ");
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			max_cnt = 0;
			map = new char[n+2][m+2];
			door = new ArrayList[26];
			key = new boolean[26];
			visited = new boolean[n+2][m+2];
			for(int i=0;i<26;i++) {
				door[i] = new ArrayList<Node>();
			}
			
			
			for(int i=0;i<n;i++) {
				String[] data = br.readLine().split("");
				for(int j=0;j<m;j++) {
					map[i+1][j+1] = data[j].charAt(0);
				}
			}
			
			
			for(int i=0;i<n+2;i++) {
				map[i][0] = '.';
				map[i][m+1] = '.';
			}
			
			for(int i=0;i<m+2;i++) {
				map[0][i] = '.';
				map[n+1][i] = '.';
			}
			
			String[] str = br.readLine().split("");
			for(int i=0;i<str.length;i++) {
				if(str[i].charAt(0) == '0') break;
				key[str[i].charAt(0) - 'a'] = true;
			}
			bfs();
			sb.append(max_cnt+"\n");
		}
		
		System.out.println(sb.toString());
	}
	
	public static void bfs() {
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(0, 0));
		visited[0][0] = true;
		while(!q.isEmpty()) {
			Node node = q.poll();
			for(int d=0;d<4;d++) {
				int nx = node.x + dx[d];
				int ny = node.y + dy[d];
				if(nx < 0 || nx >= (n+2) || ny < 0 || ny >= (m+2) || visited[nx][ny]) continue;
				if(map[nx][ny] == '*') continue;
				
                //대문자이면
                if(map[nx][ny] - 'A' >= 0 && map[nx][ny] - 'A' <= 25) {
					//키(소문자)를 가지고 있다면
                    if(key[map[nx][ny]-'A']) {
						visited[nx][ny] = true;
						map[nx][ny] = '.';
						q.add(new Node(nx, ny));
					} else {
                    //키를 안 가지고 있다면 나중에 키 얻었을 때 처리해줘야 하므로 저장
						door[map[nx][ny]-'A'].add(new Node(nx, ny));
					}
                    
                //소문자일때
				} else if(map[nx][ny] -'a' >= 0 && map[nx][ny] - 'a' <= 25) {
					int alph = map[nx][ny]-'a';
					key[map[nx][ny]-'a'] = true;
					map[nx][ny] = '.';
					visited[nx][ny] = true;
					q.add(new Node(nx, ny));

					//새로운 키 얻었으므로 저장한 대문자 처리
					for(Node d_node:door[alph]) {
						visited[d_node.x][d_node.y] = true;
						q.add(new Node(d_node.x, d_node.y));
					}
                    
                  //결과 ++
				} else if(map[nx][ny] == '$') {
					map[nx][ny] = '.';
					max_cnt++;
					visited[nx][ny] = true;
					q.add(new Node(nx, ny));
                    
                   //그냥 4방향 탐색
				} else if(map[nx][ny] == '.'){
					visited[nx][ny] = true;
					q.add(new Node(nx, ny));
				}
			}
		}
	}

}