백준 2206 <벽 부수고 이동하기>

단순하게 생각하고 구현하면 되는 전형적인 BFS, DFS문제!! 벽을 한 번까지 부수고 종점까지 가면 되는 문제

 

생각했던 방법은 총 2 가지

 

1.  방문한 배열을 visit [][][] 이렇게 구현해서 3차원 배열을 만들어 방문처리를 해서 종점까지 가는 방법
2.  dfs를 이용해서 한번 까지만 뚫고 갈 수 있게 설정해서 목적지를 탐색한다.

이 중에 첫번째 방법을 사용해서 구현을 했다.

 

우선은 좌표와 총 걸린 시간을 나타내는 t와 벽을 몇 번 부쉈는지를 표시하기 위한 num 변수로 클래스를 구성했다.

 

또한 다음 이동을 담을 Queue를 생성하고 visit의 z열 좌표는 0,1 두 가지로 벽을 1번 부순 것과 안 부순 것의 차이를 나타내기 위해 사용했다. 또한 목적지에 도달할 수 없는 경우가 있기 때문에 result는 -1로 초기화

 

그다음 큐에 시작좌표인 0,0과 1초부터 시작이기 때문에 1과 한 번도 안 부쉈기 때문에 new pont(0,0,0,1)을 넣어준다.

 

다음은 다들 아는 BFS를 시작한다

 

여기서 고려 해야 할 부분은 p.num의 횟수에 따라 처리하는 방법이다. 

 

방문할 지역이 벽이라면 p.num이 0이어야 하고 visit [x][y][0]에 방문처리를 하고 큐에 num 값을 1 증가시켜 넣어줘야 한다. 이렇게 3차원 배열을 만들어서 처리를 한다면 재방문할 일이 없기 때문에 생각보다 효율적으로 처리할 수 있다. 

 

이 문제를 변형한다면 최소한으로 벽을 부수고 목적지에 도달하는 문제도 생각할 수 있을 것 같다. 

 

이 경우에는 우선순위 큐를 사용하거나 dfs를 이용해서 풀 수 있을 것이다.

 

이문제의 경우에도 dfs로 적용해서 풀 수 있는 문제이기에 다음에 dfs로 풀어봐야겠다.

 

코드 보기

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Scanner;

public class Main{

	public static class pont {
		int x;
		int y;
		int t;
		int num;

		public pont(int x, int y, int num, int t) {
			this.x = x;
			this.y = y;
			this.t = t;
			this.num = num;
		}
	}
	static int n, m;
	static String map[];
	static Queue<pont> q;
    static int visit[][][], dir[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
	static int result = -1;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		q = new LinkedList<pont>();
		n = kb.nextInt();
		m = kb.nextInt();
		map = new String[n];
		visit = new int[n][m][2];
		for (int i = 0; i < n; i++) {
			map[i] = kb.next();
		}
		q.add(new pont(0, 0, 0, 1));
		start();
		System.out.println(result);
	}

	public static void bfs() {
		while (!q.isEmpty()) {
			pont p = q.remove();
			if(p.x==n-1&&p.y==m-1){
				result=p.t;
				return;
			}
			for (int i = 0; i < 4; i++) {
				int x1 = p.x + dir[i][0];
				int y1 = p.y + dir[i][1];
				if(x1>=0&&x1<n&&y1>=0&&y1<m&&visit[x1][y1][p.num]==0&&map[x1].charAt(y1)=='0'){
					visit[x1][y1][p.num]=1;
					q.add(new pont(x1,y1,p.num,p.t+1));
				}
				if (p.num < 1) {
					if(x1>=0&&x1<n&&y1>=0&&y1<m&&visit[x1][y1][p.num]==0&&map[x1].charAt(y1)=='1'){
						visit[x1][y1][p.num]=1;
						q.add(new pont(x1,y1,p.num+1,p.t+1));
					}
				}
				
			}
			

		}
	}

}