[BOJ - JAVA] 16933 - 벽 부수고 이동하기 3 (BFS, 그래프)

# 주소

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

16933번: 벽 부수고 이동하기 3

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
class B{
	int x;
	int y;
	int z;
	int day;
	int time;
	B(int x, int y, int z, int day, int time){
		this.x = x;
		this.y = y;
		this.z = z;
		this.day = day;
		this.time = time;
	}
}
public class Building {
	static int n, m, k;
	static int[][] arr;
	static boolean[][][] visit;
	static int[][] dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
	static Queue<B> queue;
	static int answer = Integer.MAX_VALUE;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		m = scan.nextInt();
		k = scan.nextInt();
		arr = new int[n][m];
		visit = new boolean[n][m][k + 1];
		queue = new LinkedList<B>();
		for(int i = 0; i < n; i++) {
			String str = scan.next();
			for(int j = 0; j < m; j++)
				arr[i][j] = str.charAt(j) - '0';
		}
		//입력값이 띄어쓰기 없이 주어지므로 String형태로 받아서 int형태로 저장
		bfs();
		if(answer == Integer.MAX_VALUE) System.out.print(-1);
		else System.out.print(answer);
		//answer가 max_value면 끝에 도달 못했으므로 -1출력
	}
	static void bfs() {
		queue.offer(new B(0, 0, k, 0, 1));
		visit[0][0][k] = true;
		//queue에는 차례로 x, y, k, day, time을 삽입하고 visit은 3차원배열 이용
		while(!queue.isEmpty()) {
			B now = queue.poll();
			if(now.x == n - 1 && now.y == m - 1) {
				answer = Math.min(answer, now.time);
				break;
			}
			//끝 점에 도달했을 경우 answer 출력
			for(int i = 0; i < 4; i++) {
				int nx = now.x + dir[i][0];
				int ny = now.y + dir[i][1];
				if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
				//범위 벗어나면 continue
				if(now.z > 0 &&!visit[nx][ny][now.z - 1] && arr[nx][ny] == 1 && now.day % 2 == 0) {
					queue.offer(new B(nx, ny, now.z - 1, now.day + 1, now.time + 1));
					visit[nx][ny][now.z - 1] = true;
					//벽에 부딪혔을 때 낮이면서 방문x이고 k번 이하만큼 부쉈을 때 
				}else if(!visit[nx][ny][now.z] && arr[nx][ny] == 0) {
					queue.offer(new B(nx, ny, now.z, now.day + 1, now.time + 1));
					visit[nx][ny][now.z] = true;
				}	//방문하지 않았으면서 벽이 아닌 일반 길일 때
				if(arr[nx][ny] == 1 && now.day % 2 == 1)
					queue.offer(new B(now.x, now.y, now.z, now.day + 1, now.time + 1));	
			}		//벽에 부딪혔는데 밤일 때
		}
	}
}

오랜만에 BFS를 풀이하였습니다. 안푼지 좀 오래된 거 같아서 감을 찾을겸 골드 3 ~ 골드 1 사이의 문제들로 풀었습니다.

풀다보니 백준티어도 플레티넘이 되었네요. 골드는 아무생각 없었는데 플레티넘은 좀 기분이 남다르네요 ㅋㅋ.

문제 접근 방법을 먼저 살펴보겠습니다.

 

# 문제 접근법

1. 낮과 밤을 구분해주기 위해 B라는 클래스에 매개변수로 선언한다.

2. 이를 위해 queue에 보관할 때 최초에는 0부터 삽입한다.

3. k개의 벽을 부술 수 있다고 하였으므로 k개의 벽을 부순 것 중 최단거리를 각각 배열로 표현해야 한다.

그러므로 3차원 boolean배열이 필요하다.

이렇게 요약할 수 있겠네요.

3차원 배열을 사용해야 하는 부분이 많이 어려웠을 거라 생각듭니다.

저는 과거에 벽 부수고 이동하기 1 문제를 못풀어서 풀이를 봤는데 3차원 visit을 쓰는걸 보고 많이 이해를 못했었거든요.

이번에 벽 부수고 이동하기 3 문제를 다시 풀어보니 이제야 좀 이해가 되어서 잘 풀렸습니다. 코드를 봅시다.

 

class B{
	int x;
	int y;
	int z;
	int day;
	int time;
	B(int x, int y, int z, int day, int time){
		this.x = x;
		this.y = y;
		this.z = z;
		this.day = day;
		this.time = time;
	}
}

B 클래스에는 다음과 같이 5개의 변수를 사용합니다. 

x와 y는 2차원 좌표, z는 남은 k, day는 낮과 밤, time은 최단 경로 비용입니다.

static int n, m, k;
	static int[][] arr;
	static boolean[][][] visit;
	static int[][] dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
	static Queue<B> queue;
	static int answer = Integer.MAX_VALUE;

정적 변수로는 다음과 같이 선언합니다.

visit을 제외한 대부분의 자료구조는 보통 2차원을 사용합니다.

Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		m = scan.nextInt();
		k = scan.nextInt();
		arr = new int[n][m];
		visit = new boolean[n][m][k + 1];
		queue = new LinkedList<B>();
		for(int i = 0; i < n; i++) {
			String str = scan.next();
			for(int j = 0; j < m; j++)
				arr[i][j] = str.charAt(j) - '0';
		}

n과 m을 입력받아 arr에 int형태로 저장합니다.

queue.offer(new B(0, 0, k, 0, 1));
		visit[0][0][k] = true;
		//queue에는 차례로 x, y, k, day, time을 삽입하고 visit은 3차원배열 이용
		while(!queue.isEmpty()) {
			B now = queue.poll();
			if(now.x == n - 1 && now.y == m - 1) {
				answer = Math.min(answer, now.time);
				break;
			}

중요한 것은 bfs()함수 내부입니다.

queue와 visit의 값을 각각 삽입하겠습니다.

최초의 0,0 지점에서는 무조건 낮이기 때문에 그리고 1의 시간부터 시작하기 때문에 (0,0,k,0,1)을 삽입합니다.

visit도 0,0,k를 true로 저장하는데, k번의 벽을 부술 기회가 있기 때문에 이렇게 작성하였습니다.

이 queue에서 뽑아온 값이 끝 지점에 도달하면 answer를 갱신하고 탐색을 멈춥니다.

중요한 것은 이 다음부터입니다. 이 부분에서 굉장히 헷갈리셨을 거라 생각드네요.

 

for(int i = 0; i < 4; i++) {
				int nx = now.x + dir[i][0];
				int ny = now.y + dir[i][1];
				if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
				//범위 벗어나면 continue
				if(now.z > 0 &&!visit[nx][ny][now.z - 1] && arr[nx][ny] == 1 && now.day % 2 == 0) {
					queue.offer(new B(nx, ny, now.z - 1, now.day + 1, now.time + 1));
					visit[nx][ny][now.z - 1] = true;
					//벽에 부딪혔을 때 낮이면서 방문x이고 k번 이하만큼 부쉈을 때 
				}else if(!visit[nx][ny][now.z] && arr[nx][ny] == 0) {
					queue.offer(new B(nx, ny, now.z, now.day + 1, now.time + 1));
					visit[nx][ny][now.z] = true;
				}	//방문하지 않았으면서 벽이 아닌 일반 길일 때
				if(arr[nx][ny] == 1 && now.day % 2 == 1)
					queue.offer(new B(now.x, now.y, now.z, now.day + 1, now.time + 1));	
			}		//벽에 부딪혔는데 밤일 때

첫 번째 if문에서 범위가 벗어나면 당연히 continue해주시고

두 번재 if문에서 벽에 방문했을 때 now.z값이 1이상일 때 벽을 부술 수 있으므로 다음 로직들을 실행할 수 있습니다.

또한 방문하지 않은 지점이어야 하며 낮이면서 visit의 3번째 인덱스가 now.z - 1이어야 함을 주의해주세요.

만약 이 if문이 실행된다면 queue에는 nx, ny, now.z - 1, now.day + 1, now.time + 1이 삽입됩니다.

다시 밤이 될 것입니다.

그리고 벽에 부술 수 있을 때를 앞에서 처리하였으니 이젠 벽이아닌 일반 공간을 방문했을 때를 처리해봅시다.

이 때에는 마찬가지로 visit이 false여야하며 arr가 0인 지점을 분기합니다.

queue에 삽입할 때에는 낮과 밤이 바뀌므로 nx, ny, now.z, now.day + 1, now.time + 1을 삽입합니다.

마지막으로 벽을 부술 수 없을 때를 살펴봅시다.

벽을 부술 수 없다는건.. 밤이어야 하는데 그럴 경우엔 now.z가 얼마가 있던 상관이 없다는걸 주의해주세요.

now.z가 0이든, 1이든 상관없이 밤에는 어짜피 부술 수 없습니다. 이동만 가능하지요.

따라서 벽에 방문했는데 벽이다? 그냥 그 자리에 있는 것이 최선이란 뜻입니다.

그러므로 queue에 삽입할 때에는 현재 지점인 now.x, now.y와 now.z, now.day + 1, now.time + 1을 삽입해야합니다.

주의해야할 점은 이 때 visit을 따로 처리하면 안된다는건데요.

이유는 가만히 있는 점을 삽입한다는건 그 이전에 어딘가에서 방문하여 현재의 점에 도달했다는 것이므로 그 때 이미 visit처리가 되어 있을 것이기 때문에 한 번 더 처리를 해줄 필요가 없기 때문입니다.

만약 이걸 visit으로 막는다면 제자리에 있는 점을 삽입하는 로직은 절대 실행되지 않을 것입니다.

"그럼 이게 최단거리인지 아닌지 어떻게해요?"

물론 queue에는 불필요하게 값을 넣게되기는 하지만 말이죠...

불필요한 데이터를 안넣고 어떻게 더 효율적으로 풀 수 있는지는 조금 더 연구해봐야 알 것 같습니다.

방금 우선순위큐로 now.time을 내림차순으로 정렬하여 푸는건 어떤지 해봤는데 시간 초과가 뜨는군요.

어떻게 하면 좋을지 아이디어가 있으시면 말씀해주시면 감사하겠습니다.

감사합니다.