[BOJ/Gold 2] 백준 11567 선진이의 겨울 왕국(C++)

문제 링크

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

11567번: 선진이의 겨울 왕국

문제

겨울 왕국에 나오는 올라프의 유일한 후손인 선진이는 현재 엘사가 얼려놓은 빙판길 위에 서 있다.

빙판길은 n×m의 크기를 갖는 직사각형 격자모양이고, 빙판길의 각 칸은 손상되거나 손상되지 않은 상태이다. 손상된 칸은 영대문자 X로, 손상되지 않은 칸은 . 으로 주어진다.

빙판길은 크기가 n×m인 직사각형 격자모양이고, 빙판길 각 칸의 얼음은 이미 손상되어 있거나, 손상되지 않은 상태이다.

그리고 직사각형의 행을 위에서부터 아래로 1부터 n까지, 열을 왼쪽에서부터 차례대로 1부터 m이라 가정한다.

만약 선진이가 빙판길에서 손상된 칸으로 이동하면 빙판길 아래로 추락하여 동사하기 때문에, 각 칸에 상하좌우로 인접하면서 손상되지 않은 얼음이 있는 칸으로 이동해야만 한다.

그리고 빙판의 상태가 약하기 때문에, 현재 위치에서 다른 칸으로 이동을 하면 이동하기 전 위치의 얼음은 손상된 상태로 바뀌게 된다.

그리고 (r2, c2) 에 위치한 올라프가 만든 탈출구는 빙판길 밑에 있기 때문에 (r2, c2)의 얼음을 손상 시키고, 손상된 얼음을 다시 밟아 추락해야지 탈출구를 이용할 수 있게 된다.(이미 탈출구 위의 얼음이 손상되어 있을 수도 있다.)예를 들어서 그림(a)와 같이 (1, 1)에 서 있는 선진이가 그림(b)와 같이 오른쪽으로 한 칸 이동하게 되면, 선진이의 위치는 (1, 2)가 되고 (1, 1)의 얼음은 손상되어 더 이상 지나갈 수 없게 된다. 

선진이가 있는 빙판길의 상태가 주어지고, 시작 위치 (r1, c1)와 탈출구가 있는 지점 (r2, c2) 가 주어져 있을 때, 선진이가 탈출구를 이용해 탈출이 가능한지 불가능한지 판별하는 프로그램을 작성하시오.

입력

첫 번째 줄은  두 개의 정수 n, m (1 ≤ n, m ≤ 500)이 주어진다. n은 격자에서 행의 개수를 의미하고, m은 열의 개수를 의미한다.

다음 n개의 줄에는 각각 m개의 문자로 이루어진 빙판길의 초기 상태가 주어진다. (손상된 얼음이면 'X'로 표시되고, 손상되지 않은 얼음은 '.' 으로 표시된다.)

다음 줄은 두개의 정수 r1과 c1 (1 ≤ r1 ≤ n, 1 ≤ c1 ≤ m)이 주어진다. 이는 선진이의 초기위치를 나타내고, 초기위치의 빙판길의 상태는 ‘X’로 주어진다.

다음 줄은 두개의 정수 r2과 c2 (1 ≤ r2 ≤ n, 1 ≤ c2 ≤ m)가 주어진다. 이는 올라프가 만들어 놓은 탈출구의 위치를 나타내며, 초기 위치와 일치할 수도 있다.

출력

선진이가 탈출 할 수 있다면, YES를 출력하고, 없다면 NO를 출력한다.

예제 입력 1

4 6
X...XX
...XX.
.X..X.
......
1 6
2 2

예제 출력 1

YES

예제 입력 2

5 4
.X..
...X
X.X.
....
.XX.
5 3
1 1

예제 출력 2

NO

예제 입력 3

4 7
..X.XX.
.XX..X.
X...X..
X......
2 2 
1 6

예제 출력 3

YES

예제 입력 4

1 1
X
1 1
1 1

예제 출력 4

NO

힌트

첫 번째 테스트 케이스의 경우에는 (1,6) → (2,6) →  (3,6) →  (4,6) → (4,5) → (4,4) → (4,3) →  (4,2) → (4,1) → (3,1) → (2,1) → (2,2) →  (2,3) → (1,3) → (1,2) → (2,2) 의 순서로 가면 탈출이 가능하다.

알고리즘 분류

• 그래프 탐색

풀이

visited[][] 변수를 선언하여 한 번 밟은 칸은 1 증가시킨다. 그리고 visited[][]가 1이거나 MAP[][]이 X인 경우에는 방문하지 않도록 하여, 손상된 발판은 다시 밟지 않도록 해준다.

그런데 다음 방문하고자 하는 발판이 목적지라면, 이미 손상되어 있는 발판이라면 탈출에 성공한 것이니 true를 return하고, 손상되어 있지 않은 발판이라면 방문을 한 번 더 했을 때(visited[][] == 2) true를 return하게 한다. 방문을 한 번 더 하기 위해서는 다른 발판을 방문한 후 재방문해야 하며 목적지에서 방문할 다른 발판이 없다면 탈출할 수 없다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 505
#define LL long long
#define INF 2e9

using namespace std;
int N, M, S, E;
char MAP[MAX][MAX];
pair<int, int> Start_Pos, End_Pos;
int visited[MAX][MAX];
int moveY[4] = { -1,0,1,0 };
int moveX[4] = { 0,-1,0,1 };

bool BFS(int Y, int X) {
	queue<pair<int, int> > Q;
	visited[Y][X]++;
	Q.push(make_pair(Y, X));

	while (!Q.empty()) {
		int CurY = Q.front().first;
		int CurX = Q.front().second;
		Q.pop();

		for (int i = 0; i < 4; i++) {
			int nextY = CurY + moveY[i];
			int nextX = CurX + moveX[i];
			if ((nextY >= 1) && (nextY <= N) && (nextX >= 1) && (nextX <= M)) {
				if ((nextY == End_Pos.first) && (nextX == End_Pos.second)) {
					visited[nextY][nextX]++;
					if (MAP[nextY][nextX] == 'X') {
						return true;
					}
					else {
						if (visited[nextY][nextX] == 2) {
							return true;
						}
					}
					Q.push(make_pair(nextY, nextX));
				}
				else {
					if ((visited[nextY][nextX] == 0) && (MAP[nextY][nextX] == '.')) {
						visited[nextY][nextX]++;
						Q.push(make_pair(nextY, nextX));
					}
				}
			}
		}
	};

	return false;
}

int main() {
	FIRST
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		string S;
		cin >> S;
		for (int j = 1; j <= M; j++) {
			MAP[i][j] = S[j - 1];
		}
	}
	cin >> Start_Pos.first >> Start_Pos.second;
	cin >> End_Pos.first >> End_Pos.second;
	if (BFS(Start_Pos.first, Start_Pos.second)) {
		cout << "YES" << "\n";
	}
	else {
		cout << "NO" << "\n";
	}

	return 0;
}