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

이전의 https://www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

이 문제를 풀기 전에 추천했던 문제이다.

 

이 문제의 중점은 1번 뚫은 지점과 그렇지 않은 지점 방문처리를 어떻게 해주냐?이다. 

 

이 중점의 답은 방문처리하는 vistit 2차원 배열을 안 뚫은 것을 체크하기 위한 하나, 뚫은 것을 체크하기 위한 하나 총 2개로 3차원 배열을 만드는 것이다.

이 클래스는 x,y 좌표와 시간을 담은 t , 벽을 뚫은 횟수를 담은 num으로 구성되어있다.

이렇게 p.num이 0일때는 벽을 뚫어야 할 경우가 있으면 뚫어서 다음 큐에 num에 1을 더해 넣어준다.

 

이문제를 풀면서 느낀것은 3차원 배열을 접해보지 않았던 사람들은 문제를 접근하는데 어려움이 있을 것이라고 본다.

 

3차원 배열은 간단하게 말하자면 2차원 배열이 여러개 있는 것이라고 생각을 하면 된다.

 

전체 코드

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
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 int visit[][][], dir[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
	static Queue<pont> q;
	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 start() {
		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));
					}
				}
				
			}
			

		}
	}

}