[BOJ/백준] 23563 - 벽 타기

 

23563번: 벽 타기

---

벽 타기를 하려면 내가 현재 있는 곳이 벽과 인접해야하고 내가 가야할 곳이 벽에 인접해야한다

 

최단경로를 구해야할 때 경로 중간에 최적의 경로가 생길 수 있다면 다익스트라로 구현해야한다

---

---

• 제목

벽 타기

---

• 조건

시간 제한 : 1 초

메모리 제한 : 256 MB 

---

• 문제

루시우는 높이가 H이고 너비가 W인 맵의 시작점에서 끝점까지 이동하려고 한다.

맵은 H개의 행과 W개의 열로 이루어진 격자판 모양이다. 각 칸은 벽 또는 빈칸이다.
루시우는 상, 하, 좌, 우 방향 인접한 칸으로 한 칸씩 이동할 수 있다. 벽으로는 이동할 수 없다.
루시우가 한 칸을 이동하는 데에는 1초가 걸린다.
하지만 루시우가 벽을 타고 이동하면 순식간에 (0초의 시간에) 상, 하, 좌, 우 방향 인접한 칸으로 이동할 수 있다.
어떤 빈칸의 상하좌우 중 하나가 벽이면 이 칸은 벽에 인접한 칸이라고 한다.
벽에 인접한 칸에서 벽에 인접한 칸으로 이동하면 벽을 타고 이동한다고 말한다.
루시우가 맵의 시작점에서 끝점까지 이동하는 데 걸리는 최소 시간을 구하여라.

---

• 입력

첫째 줄에는 H와 W가 공백을 사이에 두고 주어진다. 맵은 H개의 행과 W개의 열로 이루어진 격자판 모양이다.

둘째 줄부터, H개의 줄에 걸쳐서 맵의 모습을 나타내는 W개의 문자가 주어진다.

#는 벽을 뜻한다.
.는 빈칸을 뜻한다.
S는 맵의 시작점을 뜻한다. 시작점은 빈칸이다.
E는 맵의 끝점을 뜻한다. 끝점은 빈칸이다.

---

• 출력

루시우가 맵의 시작점에서 끝점까지 이동하는 데 걸리는 최소 시간을 출력하라.

---

• 힌트

1 ≤ H ≤ 500
1 ≤ W ≤ 500
격자판의 모든 칸들은 ., #, S, E 중 하나의 문자로 주어진다.
시작점 S와 끝점 E는 각각 하나씩만 주어진다.
맵의 가장 바깥 (1번째 열, W번째 열, 1번째 행, H번째 행) 칸들은 모두 벽이다.
시작점에서 끝점까지 이동할 수 없는 경우는 주어지지 않는다.

---

예제 입력1	예제 출력1
5 5 ##### #..E# #.S.# #...# #####	1

예제 입력2	예제 출력2
10 10 ########## #........# #...#....# #........# #.E....S.# #........# #........# ##.......# #........# ##########	2

---

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;

	static int H, W, S, E;
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, 1, -1};
	static char[][] arr;
	static int[][] distance;

	static void dijkstra(int start) {
		PriorityQueue<COORDINATE> pq = new PriorityQueue<>();
		distance[start / W][start % W] = 0;
		pq.add(new COORDINATE(start, 0));
		while (!pq.isEmpty()) {
			COORDINATE curr = pq.poll();
			int x = curr.index / W;
			int y = curr.index % W;
			boolean nearWallToMe = false;
			for (int k = 0; k < 4; k++) {
				int tx = x + dx[k];
				int ty = y + dy[k];
				if (tx < 0 || ty < 0 || tx >= H || ty >= W) {
					continue;
				}
				if (arr[tx][ty] == '#') {
					nearWallToMe = true;
				}
			}
			for (int k = 0; k < 4; k++) {
				boolean nearWallToYou = false;
				int tx = x + dx[k];
				int ty = y + dy[k];
				int next = tx * W + ty;
				for (int kk = 0; kk < 4; kk++) {
					int ttx = tx + dx[kk];
					int tty = ty + dy[kk];
					if (ttx < 0 || tty < 0 || ttx >= H || tty >= W) {
						continue;
					}
					if (arr[ttx][tty] == '#') {
						nearWallToYou = true;
					}
				}
				if (tx < 0 || ty < 0 || tx >= H || ty >= W) {
					continue;
				}
				if (arr[tx][ty] == '#') {
					continue;
				}
				if (distance[tx][ty] <= distance[x][y] + (nearWallToMe && nearWallToYou ? 0 : 1)) {
					continue;
				}
				distance[tx][ty] = distance[x][y] + (nearWallToMe && nearWallToYou ? 0 : 1);
				pq.add(new COORDINATE(next, distance[tx][ty]));
			}
		}
	}

	static class COORDINATE implements Comparable<COORDINATE> {
		int index;
		int distance;

		public COORDINATE(int index, int distance) {
			this.index = index;
			this.distance = distance;
		}

		@Override
		public int compareTo(COORDINATE o) {
			return Integer.compare(this.distance, o.distance);
		}
	}

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		H = Integer.parseInt(st.nextToken());
		W = Integer.parseInt(st.nextToken());

		arr = new char[H][W];
		distance = new int[H][W];
		for (int i = 0; i < H; i++) {
			String temp = br.readLine();
			for (int j = 0; j < W; j++) {
				arr[i][j] = temp.charAt(j);
				distance[i][j] = Integer.MAX_VALUE;
				if (arr[i][j] == 'S') {
					S = i * W + j;
				}
				if (arr[i][j] == 'E') {
					E = i * W + j;
				}
			}
		}
		dijkstra(S);
		System.out.println(distance[E / W][E % W]);
	}
}