[BOJ/Gold 3] 백준 23563 벽 타기(C++)

문제 링크

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

 

문제

루시우는 높이가 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

5 5
#####
#..E#
#.S.#
#...#
#####

예제 출력 1

1

 

출발하자마자 오른쪽으로 한 칸 이동하고, 위로 한 칸 벽을 타고 이동하면 총 1의 시간이 소요된다.

예제 입력 2

10 10
##########
#........#
#...#....#
#........#
#.E....S.#
#........#
#........#
##.......#
#........#
##########

 

예제 출력 2

2

 

출발하자마자 오른쪽으로 한 칸 이동하면, 벽을 타고 순식간에 끝점 왼쪽 칸으로 이동할 수 있다.

 

알고리즘 분류

• 그래프 탐색

 

풀이

벽과 인접한 칸끼리는 이동할 때 비용이 0이고, 그게 아니라면 이동할 때 비용이 1이므로 0-1 BFS를 사용한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <algorithm>
#define MAX 501
#define INF 1e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int H, W;
int MAP[MAX][MAX];
bool isAdjacent[MAX][MAX];
int Visited[MAX][MAX];
pair<int, int> Start;
int MoveY[4] = { -1,0,1,0 };
int MoveX[4] = { 0,-1,0,1 };
int Answer = INF;

void init() {
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			Visited[i][j] = INF;
		}
	}
}

void input() {
	cin >> H >> W;
	for (int i = 0; i < H; i++) {
		string S;
		cin >> S;
		for (int j = 0; j < W; j++) {
			if (S[j] == '#') {
				MAP[i][j] = -1;
			}
			else if (S[j] == 'S') {
				Start = make_pair(i, j);
			}
			else if (S[j] == 'E') {
				MAP[i][j] = 1;
			}
		}
	}
}

void bfs() {
	deque<pair<pair<int, int>, int> > DQ;
	DQ.push_front(make_pair(Start, 0));
	Visited[Start.first][Start.second] = 0;

	while (!DQ.empty()) {
		int NowY = DQ.front().first.first;
		int NowX = DQ.front().first.second;
		int NowT = DQ.front().second;
		DQ.pop_front();

		if (MAP[NowY][NowX] == 1) {
			Answer = NowT;
			return;
		}

		for (int i = 0; i < 4; i++) {
			int NextY = NowY + MoveY[i];
			int NextX = NowX + MoveX[i];
			if ((NextY >= 0) && (NextY < H) && (NextX >= 0) && (NextX < W) && (MAP[NextY][NextX] != -1)) {
				if (isAdjacent[NowY][NowX] && isAdjacent[NextY][NextX]) {
					if (Visited[NextY][NextX] > NowT) {
						DQ.push_front(make_pair(make_pair(NextY, NextX), NowT));
						Visited[NextY][NextX] = NowT;
					}
				}
				if (Visited[NextY][NextX] > NowT + 1) {
					DQ.push_back(make_pair(make_pair(NextY, NextX), NowT + 1));
					Visited[NextY][NextX] = NowT + 1;
				}
			}
		}
	};
}

void settings() {
	for (int i = 1; i < (H - 1); i++) {
		for (int j = 1; j < (W - 1); j++) {
			int Wall = 0;
			for (int k = 0; k < 4; k++) {
				int NextY = i + MoveY[k];
				int NextX = j + MoveX[k];
				if (MAP[NextY][NextX] == -1) {
					Wall++;
				}
			}
			if (Wall > 0) {
				isAdjacent[i][j] = true;
			}
		}
	}
	bfs();
}

void printAnswer() {
	if (Answer == INF) {
		cout << "-1\n";
	}
	else {
		cout << Answer << "\n";
	}
}

int main() {
    FASTIO

	init();
	input();
	settings();
    printAnswer();

    return 0;
}