BOJ - 열쇠 9328번 (JAVA)

❓ 문제 - 백준 열쇠 9328번 - JAVA 풀이법

 

출처 

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

9328번: 열쇠

 

 

📝 문제해결법

1. 이 문제는 BFS로 해결했다.

• 가장자리에서 출입이 가능하기 때문에 코드의 간결함을 위해 map을 상,하,좌,우 한 칸씩 늘려주고 그곳을 '.'로 채운 후 0,0 에서 bfs를 시작하도록 구현하였다.
• 일반 BFS 풀이와 같이 visited 2차원 배열로 방문체크를 하고, key의 boolean 배열로 'A' ~ 'Z'까지의 문을 열 수 있는 키를 가지고 있는지 체크하였다.
• 또한, door라는 ArrayList를 담는 배열을 선언해줘서, 방문은 했지만 아직 키가 없어서 통과못하는 문에 대한 Node(x, y)를 add 해줬다.
• 우선 q에서 하나씩 노드를 꺼내 4방향으로 탐색을 하는데 만약 범위를 넘거나, 이미 방문한 곳, 벽(*)이라면 continue
• 만약 문('A' ~ 'Z')라면 문을 열 수 있는 키가 존재하면 방문 하고, 만약 문을 열 수 없는 키가 존재하지 않는다면 door 배열에 해당 위치 정보 Node를 add해준다.
• 그리고 탐색지역에 열쇠('a' ~ 'z')가 있다면 열쇠를 가지고, 만약 과거에 주운 열쇠를 가지고 열 수 있는 문을 방문할 수 있다면 그곳에 방문하도록 q에 해당 위치정보를 door에서 get하여 add 해준다.
• 또한 이동할 곳에 문서가 있다면 cnt를 1 증가시켜주고, 빈칸(.) 지역이라면 이동처리해준다.

 

2. 느낀점

• 방문처리에 대해서 고민이 많았다. 사실 이동하다가 열쇠를 가지고 있지 않아서 문을 못 열었는데 다른 곳으로 이동하다가 열쇠를 줍고 다시 그곳을 이동하려면 방문처리가 되어 있어서 가지 못하기 때문이다. 그러나 방문처리를 아예 안 해주면 큐에서 무한으로 Node가 add 되기 때문에 이것또한 잘못된 풀이다. 사실 이 부분에 1시간 이상 고민을 하다가 다른 사람의 풀이를 대충 훑었는데 visited 2차원 배열로 한번에 처리해주고, 이동하다 열지못한 문에 대한 정보를 넣어주다가 해당 열쇠를 가지면 어차피 이동했던 곳이므로 그곳에 이동가능하니 큐에 넣어주면 된다 ! 이런 아이디어성 풀이를 보고 조금 감동을 했다. 저번에 문제를 풀다가 이런 비슷한 문제를 만났는데 이런 식으로 방문처리에 신경 쓰지말고 왔다 갔다하는 부분에 아이디어 로직을 집어 넣으면 되는구나 느꼈다.

 

💻 소스코드 (JAVA)

// BOJ - 열쇠(9328번)
// 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));
				} else if(map[nx][ny] == '.'){
					visited[nx][ny] = true;
					q.add(new Node(nx, ny));
				}
			}
		}
	}

}