[백준 1194] 달이 차오른다, 가자. (자바)

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

1194번: 달이 차오른다, 가자.

 

난이도 : 골드 1

 

Set을 이용한 BFS로 문제를 풀다가 오류를 만났습니다. 도저히 방법이 없어 검색해보니 비트 마스킹으로 쉽게 풀 수 있는 문제였습니다.

방문 검사는 3차원 배열을 통해 진행합니다. a~f까지 6개의 열쇠가 있으므로 [N][M][111111]의 크기를 가집니다.

비트 연산을 통해 key를 저장하고 문을 여는 것이 목표입니다.

key를 넣는 과정은 or 연산(1 << 열쇠 - 'a')이고 문을 여는 과정은 and 연산(1 << 문 - 'A')입니다.

 

a, c 열쇠를 넣고 B, C 문을 열어보겠습니다.

초기값은 000000(0)입니다. a는 1 << 0 = 1이므로 or 연산을 하면 key 값은 000001(1)이 됩니다.

c는 1 << 2 = 4이므로 or 연산을 하면 key 값은 000101(5)이 됩니다.

 

B의 문은 1 << 1 = 000010(2)의 값을 가집니다. 000101 & 000010 == 0 이므로 b가 없기 때문에 통과할 수 없습니다.

C의 문은 1 << 2 = 000100(4)의 값을 가집니다. 000101 & 000100 != 0 이므로 c를 가지고 있어 통과할 수 있습니다.

 

이를 통해 현재의 key값으로 방문 여부를 확인할 수 있습니다.

---

전역 변수

int n, m = 맵의 크기

char map[][] = 입력으로 주어진 맵

int dx[], dy [] = 4방향으로 이동할 수 있는 배열

 

메소드

void main

입력을 받고 map을 구성합니다. 그리고 출발 위치를 x, y에 저장합니다.

(escape 호출)

 

void escape

큐를 만들고 한 턴을 구분하는 -1, -1을 넣어주고 방문을 관리하는 visit배열을 선언합니다.

BFS를 진행하며 현재 위치가 1이거나 큐가 빌 때까지 진행합니다.

4방향으로 이동하며 유효한 범위에서 열쇠를 만나면 key에 넣어줍니다.

만약 문을 만난다면 열쇠와 비교하고 열쇠를 가지고 있다면 방문합니다.

(check 호출)

 

boolean check

현재 범위가 유효하고 이 칸에 '#'(벽)이 없는지 확인해줍니다.

 

class Point

현재 좌표 x, y와 현재 키 값을 저장합니다.

 

 

	import java.io.BufferedReader;
	import java.io.InputStreamReader;
	import java.util.*;
	public class p1194 {
	static int n, m;
	static char map[][];
	static int dx[] = {-1,1,0,0};
	static int dy[] = {0,0,-1,1};
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer stz = new StringTokenizer(br.readLine());
	n = Integer.parseInt(stz.nextToken());
	m = Integer.parseInt(stz.nextToken());
	map = new char[n][m];
	int x = -1;
	int y = -1;
	for(int i = 0; i < n; i++) {
	String input = br.readLine();
	for(int j = 0; j < m; j++) {
	map[i][j] = input.charAt(j);
	if(map[i][j] == '0') {
	x = i;
	y = j;
	}
	}
	}
	escape(x, y);
	}
	public static void escape(int x, int y) {
	Queue<Point> q = new LinkedList<>();
	q.offer(new Point(-1, -1, 0));
	q.offer(new Point(x, y, 0));
	boolean visit[][][] = new boolean[n][m][1 << 6];
	visit[x][y][0] = true;
	int count = -1;
	while(!q.isEmpty()) {
	Point now = q.poll();
	if(now.x == -1) {
	count++;
	if(!q.isEmpty())
	q.offer(now);
	continue;
	}
	if(map[now.x][now.y] == '1') {
	System.out.println(count);
	return;
	}
	for(int i = 0; i < 4; i++) {
	int nx = now.x + dx[i];
	int ny = now.y + dy[i];
	int key = now.key;
	int copy = key;
	if(check(nx, ny) && !visit[nx][ny][key]) {
	//열쇠
	if(map[nx][ny] >= 'a' && map[nx][ny] <= 'z') {
	key |= (1 << map[nx][ny] - 'a');
	visit[nx][ny][key] = true;
	q.offer(new Point(nx, ny, key));
	}
	//문
	else if(map[nx][ny] >= 'A' && map[nx][ny] <= 'Z') {
	if(!((key & (1 << map[nx][ny] - 'A')) == 0)) {
	visit[nx][ny][key] = true;
	q.offer(new Point(nx, ny, key));
	}
	}
	//빈 칸
	else {
	q.offer(new Point(nx, ny, key));
	visit[nx][ny][key] = true;
	}
	}
	key = copy;
	}
	}
	System.out.println(-1);
	}
	public static boolean check(int x, int y) {
	return x >= 0 && y >= 0 && x < n && y < m && map[x][y] != '#';
	}
	static class Point {
	int x, y, key;
	Point(int x, int y, int key) {
	this.x = x;
	this.y = y;
	this.key = key;
	}
	}
	}

view raw p1194.java hosted with ❤ by GitHub