[백준] 14923. 미로 탈출 (골드4) - BFS

Kiefer Sol·2024년 8월 17일

목록 보기

33/35

14923. 미로 탈출 (골드4)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	5512	2139	1604	37.964%

문제

홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 있어 홍익이가 탈출하기 어렵게 하고 있다.

홍익이는 마법사의 연구실에서 훔친 지팡이가 있어, 벽을 길로 만들 수 있다. 그렇지만, 안타깝게도 마법의 지팡이는 단 한 번만 사용할 수 있다.

이때, 홍익이를 도와 미로에서 탈출할 수 있는지 알아보고, 할 수 있다면 가장 빠른 경로의 거리 D는 얼마인지 알아보자.

인접한 칸으로 이동하는데 똑같은 시간이 들고, 벽을 부수는 데 시간이 걸리지 않는다.

입력

N M
Hx Hy
Ex Ey
N X M 행렬

2 ≤ N ≤ 1000, 2 ≤ M ≤ 1000
1 ≤ Hx, Hy, Ex, Ey ≤ 1000
(Hx, Hy)≠ (Ex, Ey)
행렬은 0과 1로만 이루어져 있고, 0이 빈 칸, 1이 벽이다.

출력

D (탈출 할 수 없다면, -1을 출력한다.)

예제 입력 1
5 6
1 1
5 6
0 1 1 1 0 0
0 1 1 0 0 0
0 1 0 0 1 0
0 1 0 0 1 0
0 0 0 1 1 0

예제 출력 1
11

풀이

3차 방문배열과 클래스를 만들어 x축, y축, 점프마법 사용여부 체크
위치가 벽이면 아직까지 마법을 사용 안했고, 방문하지 않았다면 마법써서 탈출
위치가 벽이 아니면 마법 사용안해도 되서 마법 사용여부 확인 안하고 방문체크
=> 클래스에 기존 방문여부를 넣어가면서 마법 사용여부를 이어간다.

public class Search_14923 {
	public static int N, M, Hx, Hy, Ex, Ey;
	public static int[][] map; // 위치배열
	public static int[][][] visited; // 3차 방문배열 => x,y축, 마법 사용여부
	public static Queue<Point> que = new LinkedList<Point>();
	public static int[] dx = { -1, 1, 0, 0 };
	public static int[] dy = { 0, 0, -1, 1 };
	public static int minTime = Integer.MAX_VALUE;

	public static class Point {
		public int x;
		public int y;
		public int jump; // 마법사용여부

		public Point(int x, int y, int jump) {
			this.x = x;
			this.y = y;
			this.jump = jump;
		}
	}

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new int[N][M];
		visited = new int[N][M][2];

		st = new StringTokenizer(br.readLine());
		Hx = Integer.parseInt(st.nextToken()) - 1;
		Hy = Integer.parseInt(st.nextToken()) - 1;

		st = new StringTokenizer(br.readLine());
		Ex = Integer.parseInt(st.nextToken()) - 1;
		Ey = Integer.parseInt(st.nextToken()) - 1;

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		BFS();

		if (minTime == Integer.MAX_VALUE)
			System.out.println(-1);
		else
			System.out.println(minTime);

	}

	public static void BFS() {
		que.offer(new Point(Hx, Hy, 0));
        
        // 시작점은 각각의 위치와 마법 사용했을 때, 안했을 때 둘 다 체크
		visited[Hx][Hy][0] = 1;
		visited[Hx][Hy][1] = 1;
		
		int second = 0;
        
        //반복문을 한번 돌 때마다 시간이 1초씩 흐른다.
		while (!que.isEmpty()) {
			second++;
		// System.out.println(second);
	
			int len = que.size();
			for (int s = 0; s < len; s++) {
				Point now = que.poll();

				for (int i = 0; i < 4; i++) {
					int nx = now.x + dx[i];
					int ny = now.y + dy[i];
                    
                    // 탈출위치면 리턴
					if (nx == Ex && ny == Ey) {
						minTime = second;
						return;
					}
					if (nx < 0 || ny < 0 || nx >= N || ny >= M)
						continue;
					// 벽
					if (map[nx][ny] == 1) {
                    	// 아직까지 마법을 사용 안했고, 방문하지 않았다면 마법써서 탈출
						if (now.jump == 0 && visited[nx][ny][1] == 0) {
							que.offer(new Point(nx, ny, 1));
							visited[nx][ny][1] = 1; // 위치에서 마법 사용함
						}
					}
					// 빈칸
					else {
                    	// 벽이 아니라 마법 사용안해도 되서 마법 사용여부 확인 안함
						if (visited[nx][ny][now.jump] == 0) {
							que.offer(new Point(nx, ny, now.jump));
							visited[nx][ny][now.jump] = 1; // 마법사용여부 전에와 같이 유지
						}
					}
				}
			}
		}
	}
}