[ 백준 9328 ] 열쇠

 

1. 문제: https://www.acmicpc.net/problem/9328

9328번: 열쇠

 

2. 풀이

지도 상에서 돌아다니면서 문을 만났을 때 열쇠가 있다면 열고 들어가고 없으면 열지 못하는 본 문제와 비슷한 유형의 문제를 백준에서 풀었던 기억이 있다. 그 문제가 뭐였는지 기억한다면 첨부하도록 하겠다....

 

아무튼 문제의 상근이가 문서를 훔치기 위해서 빌딩 내부를 돌아다녀야 하는데 문제의 중요한 몇 가지만 인지하고 있다면 크게 어려울 것은 없다.

 

1) 상근이의 출발점이 정해지지 않았으며, 빌딩 가장자리의 빈 공간이나 문을 통해 드나들 수 있다.

-> 주어진 빌딩 지도를 빈 공간으로 한 번 둘러싸고 (0, 0)을 출발점으로 잡아준다.

 

2) 열쇠의 사용횟수는 제한이 없다.

-> 'a - z'에 해당하는 열쇠를 갖고 있는지의 여부를 알고 있을 필요가 있다.

-> 단순하게 boolean 배열을 사용해도 되지만 얼마전에 비트마스크 포스팅을 한 만큼 비트마스크를 활용해본다.

 

3) BFS는 방문한 노드를 재방문하지 않을 것인데 어떻게 재탐색을 시킬 것인가?

-> 두 가지 방법이 있다.

 

 3-1) Literally 재탐색

 필자가 처음 생각했던 방식은 다음과 같다.

• 처음 입력을 받을 때, 문의 위치(알파벳 대문자)들을 저장해두고, 이미 가지고 있는 열쇠를 입력 받으면 해당 열쇠로 열 수 있는 문은 다 열어둔다.
• 탐색을 진행하면서 새로운 열쇠를 발견한다면, 그 지점부터 다시 탐색을 시작한다.

 3-2) 쪼금 더 영리하게

 위 풀이는 문제에서는 테스트케이스와 너비(w) 그리고 높이(h)가 모두 max 100으로 제한되어 있어서 가능했던 것 같기도 하다. 문서를 훔치기 위한 거리를 계산해야 했다면 위 방법을 써야됐을지도 모르겠다. 하지만 결과적으로 원하는 것은 '몇 개의 문서를 훔칠 수 있느냐' 이기 때문에 굳이 재탐색을 실행할 필요는 없다.

• (0, 0)에서 탐색을 시작하고 진행하면서 열쇠를 갖고 있지 않은 문을 만났을 경우 이 문의 위치를 배열에 담아둔다.
• 열쇠가 있는 문을 만났을 경우 문을 따고 탐색을 계속 진행한다.
• 열쇠를 발견했을 경우, 해당 열쇠로 열 수 있는 지금까지 만난 모든 문을 따고 이를 큐(Queue)에 집어 넣는다.
• 열쇠를 얻음으로써 새롭게 열린 문으로부터 탐색을 이어서 진행함에 따라, 문을 따기 위해 다시 번거롭게 돌아가는 탐색을 수행하지 않게 된다.

 이 두 번째 방법에서 가장 중요한 것은, 열쇠를 얻었을 경우 탐색을 진행하는 동안 발견한 문만 연다는 것이다. 이 부분에 대해 조금 생각해본다면 어렵지 않게 풀 수 있다.

 

3. 코드

cf) 비트마스크로 키(key) 목록 갱신 및 키 소유 여부 확인

//핵심 로직 예시(아래 전체 코드에서는 변수명을 달리 사용함)
//키(key) 업데이트
char c = map[i][j];
if(c >= 'a' && c <= 'z') {
	key |= (1 << (c - 'a'));
}

//키(key) 소유 여부 확인
char door = map[i][j];
if(door >= 'A' && door <= 'Z'){
  if((key & (1 << (door - 'A'))) != 0){
      System.out.println("키 있음");
  }
}

전체코드 1. bfs 여러번 돌기

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

public class Key9328 {
	static int N, M, key = 0, ans;
	static int dy[] = {-1, 0, 1, 0};
	static int dx[] = {0, 1, 0, -1};
	static char map[][];
	static LinkedList<Point> doors[];
	
	static void bfs(int y, int x, boolean visit[][]) {
		Queue<Point> q = new LinkedList<Point>();
		q.add(new Point(y, x));
		visit[y][x] = true;
		while(!q.isEmpty()) {
			Point now = q.poll();
			if(map[now.y][now.x] == '$') {
				ans++;
				map[now.y][now.x] = '.';
			}
			for(int dir = 0; dir<4; dir++) {
				int ny = now.y + dy[dir];
				int nx = now.x + dx[dir];
				if(ny < 0 || nx < 0 || ny >= N+2 || nx >= M+2 || visit[ny][nx] || map[ny][nx] == '*')
					continue;
				char tmp = map[ny][nx];
				//문을 만났는데 열쇠가 있다면
				if(tmp >= 'A' && tmp <= 'Z' && (key & (1 << (tmp - 'A'))) != 0) {
					map[ny][nx] = '.';
					visit[ny][nx] = true;
					q.add(new Point(ny, nx));
				}
				//기존에 없던 열쇠를 찾는다면
				if(tmp >= 'a' && tmp <= 'z') {
					if((key & (1 << (tmp - 'a'))) == 0) {
						key |= (1 << (tmp - 'a'));
						map[ny][nx] = '.';
						boolean visit2[][] = new boolean[N+2][M+2];
						bfs(ny, nx, visit2);
					}else {
						map[ny][nx] = '.';
						visit[ny][nx] = true;
						q.add(new Point(ny, nx));
					}
				}
				if(tmp == '.' || tmp == '$') {
					visit[ny][nx] = true;
					q.add(new Point(ny, nx));
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int testCase = Integer.parseInt(br.readLine());
		while(testCase-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			map = new char[N+2][M+2];
			doors = new LinkedList[26];
			key = 0;
			ans = 0;
			for(int i = 0; i<26; i++)
				doors[i] = new LinkedList<Point>();
			for(int i = 0; i<N+2; i++) {
				if(i == 0 || i == N+1) {
					Arrays.fill(map[i], '.');
					continue;
				}
				String str = br.readLine();
				for(int j = 0; j<M+2; j++) {
					if(j == 0 || j == M+1) {
						map[i][j] = '.';
						continue;
					}
					map[i][j] = str.charAt(j - 1);
					if(map[i][j] >= 'A' && map[i][j] <= 'Z') {
						doors[map[i][j] - 'A'].add(new Point(i, j));
					}
				}
			}
			String keys = br.readLine();
			if(!keys.equals("0")) {
				for(int i = 0; i < keys.length(); i++) {
					int tmp = keys.charAt(i) - 'a';
					key |= (1 << tmp);
					if(doors[tmp].size() > 0) {
						for(Point p : doors[tmp])
							map[p.y][p.x] = '.';
					}
				}
			}
			boolean visit[][] = new boolean[N+2][M+2];
			bfs(0, 0, visit);
			bw.write(String.format("%d\n", ans));
		}
		bw.flush();
		bw.close();
		br.close();
	}
	
	static class Point {
		int y;
		int x;
		public Point(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}
}

 

 

전체코드 2. bfs 한번만 돌기

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

public class Key9328 {
	static int N, M, key, ans;
	static int dy[] = {-1, 0, 1, 0};
	static int dx[] = {0, 1, 0, -1};
	static char map[][];
	static LinkedList<Point> doors[];
	
	static void bfs(int y, int x, boolean visit[][]) {
		Queue<Point> q = new LinkedList<Point>();
		q.add(new Point(y, x));
		visit[y][x] = true;
		while(!q.isEmpty()) {
			Point now = q.poll();
			for(int dir = 0; dir<4; dir++) {
				int ny = now.y + dy[dir];
				int nx = now.x + dx[dir];
				if(ny < 0 || nx < 0 || ny >= N+2 || nx >= M+2 || visit[ny][nx] || map[ny][nx] == '*')
					continue;
				char tmp = map[ny][nx];
				if(tmp >= 'A' && tmp <= 'Z') { //문을 만났을 때
					if((key & (1 << (tmp - 'A'))) != 0) { //키가 있다면
						map[ny][nx] = '.';
						visit[ny][nx] = true;
						q.add(new Point(ny, nx));
					} else {
						doors[tmp - 'A'].add(new Point(ny, nx));
					}
				} else if(tmp >= 'a' && tmp <= 'z') { //열쇠를 만났을 때
					int idx = (int)tmp - 'a';
					key |= (1 << idx);
					visit[ny][nx] = true;
					q.add(new Point(ny, nx));
	
					for(Point p : doors[idx]) { //발견한 문들 중 줏은 열쇠에 해당하는거 다 따버리기
						if(!visit[p.y][p.x] && map[p.y][p.x] == (char)(idx + 'A') ) {
							map[p.y][p.x] = '.';
							visit[p.y][p.x] = true; 
							q.add(p);
						}
					}
				} else if(tmp == '.'){
					visit[ny][nx] = true;
					q.add(new Point(ny, nx));
				} else {
					ans++;
					map[ny][nx] = '.';
					visit[ny][nx] = true;
					q.add(new Point(ny, nx));
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int testCase = Integer.parseInt(br.readLine());
		while(testCase-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			map = new char[N+2][M+2];
			doors = new LinkedList[26];
			key = 0;
			ans = 0;
			for(int i = 0; i<26; i++)
				doors[i] = new LinkedList<Point>();
			for(int i = 0; i<N+2; i++) {
				if(i == 0 || i == N+1) {
					Arrays.fill(map[i], '.');
					continue;
				}
				String str = br.readLine();
				for(int j = 0; j<M+2; j++) {
					if(j == 0 || j == M+1) {
						map[i][j] = '.';
						continue;
					}
					map[i][j] = str.charAt(j - 1);
				}
			}
			String keys = br.readLine();
			if(!keys.equals("0")) {
				for(int i = 0; i < keys.length(); i++) {
					int tmp = keys.charAt(i) - 'a';
					key |= (1 << tmp);
				}
			}
			boolean visit[][] = new boolean[N+2][M+2];
			bfs(0, 0, visit);
			bw.write(String.format("%d\n", ans));
		}
		bw.flush();
		bw.close();
		br.close();
	}
	
	static class Point {
		int y;
		int x;
		public Point(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}
}

확실히 본 문제에서는 두 번째 방법이 효율적이다