[백준 2206] 벽 부수고 이동하기 (JAVA)

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

2206번: 벽 부수고 이동하기

 

 

기존의 다른 탐색문제와 마찬가지로 현재 정점에서 한번에 이동할수 있는 정점들이 정해져있는 문제이다.

 

조금 특이한 부분은 이동할수 없는 '벽'으로 처리된 부분을 단 한번 부수고 이동이 가능하다는 점이다.

 

이런 부분 때문에 이 문제가 조금 어렵게 느껴질 수 있는데

 

이 문제를 풀기 위한 아이디어는 그냥 단순히 벽을 부수지 않고 이동하는 경우와 한번 벽을 부순 경우를 둘로 나누어

탐색을 진행하면 된다는것이다.

 

즉, 현재 정점에서 이동할 다음 정점에 대해 판별할때 다음 정점이 벽인 경우와 벽이 아닌경우로 나누어 

탐색을 진행하면 된다. 이때 벽이 아닌경우는 현재 정점이 벽을 부순적이 있든 없든 상관 없지만

벽인 경우는 현재정점은 벽을 부순적이 없는 경우에 대해서만 탐색을 하면 된다.

 

그럼 이 아이디어를 그대로 코드로 옮겨 보도록 하겠다.

 

먼저 벽을 부순경우와 아닌경우를 구분하기 위해 방문처리할 배열을 3차원 배열로 선언하도록 하겠다.

현재 문제는 벽을 단 한번만 부술수 있기 때문에 3차원 배열이면 충분하다.

 

	static int[][][] metrix;

 

또 상하좌우로 이동할수 있으므로 dx, dy 배열도 같이 선언해주고,

 

	static int[] dx = { 1 , 0 , -1 , 0 };
	static int[] dy = { 0 , 1 , 0 , -1 };

 

BFS를 사용한 탐색을 진행할것이므로 

큐에 삽입할때 벽을 부수었는가에대한 정보도 같이 넣어주기 위해 별도의 클래스를 하나 선언해주고 

큐로 사용할 배열도 만들어주도록 하겠다.

 

class ChkPoint{
	
	int x;
	int y;
	int w;
	
	ChkPoint(int x, int y, int w){
		this.x = x;
		this.y = y;
		this.w = w;
	}
}

 

	static int front, rear, n, m, size;
	static ChkPoint[] queue;

 

 

큐와 방문배열에 대해 동적으로 메모리를 할당할 메소드도 만들어주겠다.

 

	static void init() {
		size = n*m;
		queue = new ChkPoint[size];
		metrix = new int[2][n][m];
	}

 

 

이제 BFS를 사용해 탐색할 메소드를 만들어주겠다.

 

시작지점이 목표지점이라면 바로 리턴,

목표지점에 도달한다면 바로 최단거리를 리턴해줄수 있도록 리턴해주고

모든 탐색이 끝난 경우에 도달하지 못했다면 -1를 리턴해줄수 있도록 메소드를 작성한다.

 

BFS 알고리즘에 대해서는 이전에 작성한 BFS 구현과 다를게 없으니 생략하도록 하겠다.

 

https://0bliviat3.tistory.com/16

BFS(너비 우선 탐색) 구현 (JAVA)

- 참고

 

	static int bfs() {
		if(n == 1 && m == 1 && metrix[0][0][0] == 0) return 1;
		
		queue[rear++] = new ChkPoint(0,0,0);
		metrix[1][0][0] = metrix[0][0][0] = 1;
		
		while(queue[front] != null) {
			ChkPoint edge = queue[front];
			int dis = metrix[edge.w][edge.x][edge.y] + 1;
			queue[front++] = null;
			front%=size;			
			for(int i = 0; i < 4; i++) {
				int x = edge.x + dx[i];
				int y = edge.y + dy[i];

				if(x == n - 1 && y == m - 1) return dis; // 목표지점 도달했다면 탐색 종료
				
				if(x >= 0 && y >= 0 && x < n && y < m) { // 기본적으로 범위안인가 체크
					if(metrix[edge.w][x][y] == 1 && edge.w == 0) { // 다음 정점이 벽이고 현재 벽을 부순적 없는 경우
						queue[rear++] = new ChkPoint(x,y,1); // 벽을 부순 정점 큐에 삽입
						rear%=size;
						metrix[1][x][y] = dis; // 벽을 부순경우를 관리할 행렬로 방문처리
					}else if(metrix[edge.w][x][y] == 0) { // 다음 정점이 벽이 아닌 경우
						queue[rear++] = new ChkPoint(x,y,edge.w);
						rear%=size;
						metrix[edge.w][x][y] = dis;
					}
				}
			}
		}
		return -1;
	}

 

 

그럼 주어진 예제에 대해 잘 출력하는지 확인해보면

 

 

맞게 답을 출력하는것을 확인할수 있다.

 

아래는 코드의 전문이다.

 

package boj3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj2206 {
	
	/*
	 * 제출 完
	 */
	
	static int front, rear, n, m, size;
	
	static int[][][] metrix;
	
	static ChkPoint[] queue;
	
	static int[] dx = { 1 , 0 , -1 , 0 };
	static int[] dy = { 0 , 1 , 0 , -1 };
	
	static void init() {
		size = n*m;
		queue = new ChkPoint[size];
		metrix = new int[2][n][m];
	}
	
	static int bfs() {
		if(n == 1 && m == 1 && metrix[0][0][0] == 0) return 1;
		
		queue[rear++] = new ChkPoint(0,0,0);
		metrix[1][0][0] = metrix[0][0][0] = 1;
		
		while(queue[front] != null) {
			ChkPoint edge = queue[front];
			int dis = metrix[edge.w][edge.x][edge.y] + 1;
			queue[front++] = null;
			front%=size;			
			for(int i = 0; i < 4; i++) {
				int x = edge.x + dx[i];
				int y = edge.y + dy[i];

				if(x == n - 1 && y == m - 1) return dis; // 목표지점 도달했다면 탐색 종료
				
				if(x >= 0 && y >= 0 && x < n && y < m) { // 기본적으로 범위안인가 체크
					if(metrix[edge.w][x][y] == 1 && edge.w == 0) { // 다음 정점이 벽이고 현재 벽을 부순적 없는 경우
						queue[rear++] = new ChkPoint(x,y,1); // 벽을 부순 정점 큐에 삽입
						rear%=size;
						metrix[1][x][y] = dis; // 벽을 부순경우를 관리할 행렬로 방문처리
					}else if(metrix[edge.w][x][y] == 0) { // 다음 정점이 벽이 아닌 경우
						queue[rear++] = new ChkPoint(x,y,edge.w);
						rear%=size;
						metrix[edge.w][x][y] = dis;
					}
				}
			}
		}
		return -1;
	}
	
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		init();
		
		for(int i = 0; i < n; i ++) {
			String now = in.readLine();
			for(int j = 0; j < m; j++) {
				metrix[0][i][j] = metrix[1][i][j] = now.charAt(j) - '0';
			}
		}
		
		in.close();
		
		System.out.print(bfs());
	}

}

class ChkPoint{
	
	int x;
	int y;
	int w;
	
	ChkPoint(int x, int y, int w){
		this.x = x;
		this.y = y;
		this.w = w;
	}
}