[백준 11567] 선진이의 겨울 왕국

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

11567번: 선진이의 겨울 왕국

#include <cstdio>
#include <queue>
int R, C;
char board[500 + 2][500 + 2];
int sx, sy;
int ex, ey;

struct _st
{
	int x, y;
};

std::queue<_st> Q;


void input()
{
	scanf("%d %d", &R, &C);
	for (int i = 1; i <= R; i++) {
		scanf("%s", &board[i][1]);
	}
	scanf("%d %d %d %d", &sx, &sy, &ex, &ey);

}

bool BFS()
{
	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };

	Q.push({ sx ,sy });

	while (!Q.empty()) {
		_st data = Q.front();
		//printf("%d %d\n", data.x, data.y);
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 1 || nx > R || ny < 1 || ny > C) continue;
			if (nx == ex && ny == ey && board[ex][ey] == 'X') return true;
			if (board[nx][ny] == 'X') continue;
			Q.push({ nx, ny });
			board[nx][ny] = 'X';
		}
	}
	return false;
}



int main()
{
	input();
	if (!BFS()) printf("NO\n");
	else printf("YES\n");
	return 0;
}

쉬운 문제를 어렵게 생각하지 말자.. 

처음에는 선진이가 지나온 경로가 중요한 줄 알고 BFS를 2번 돌리려고 했다.

이 문제는 목적 위치의 상태가 'X' 일 때 한번 더 방문할 수 있다면 true, 없다면 false를 리턴하는 문제이다. 

 

사실 방문 배열도 필요없다. 

지나온 길은 다시 되돌아 갈 수 없으므로 (이미 얼음이 손상되었으므로) 입력받은 보드의 해당 칸을 'X'로 바꿔준다. 

그리고 빈칸인지 / 목적위치인지 관계없이 일단 상태발전을 시킨다. 

만약 현재 칸에서 상태발전 시키려는 곳이 목적 위치인 동시에, board[ex][ey] == 'X' 일때는 목적 위치에 두 번 방문하여(혹은 입력받을 때 부터 이미 손상되어서 한번만 방문하면 되어서) 탈출할 수 있는 경우이다. 따라서 true를 리턴한다. 

그게 아니라면 Q를 빠져나온 후 에 false를 리턴한다. 

당연하게도 위의 조건은 if(board[nx][ny] == 'X') continue; 조건문 "전"에 확인해주어야 한다!

 

---

++ 22.11.12 추가 방문 배열을 사용한 코드 

방문배열을 사용할 때는 board에서 X인 부분을 방문처리 해주었다. 

그래야 목적 위치의 칸이 이미 X일때 한번 도착했을 때 바로 탈출할 수 있다. (이렇게 처리 안해주면 예제3번에서 걸림)

#include <cstdio>
#include <queue>
int R, C;
char board[500 + 2][500 + 2];
int sx, sy;
int ex, ey;

struct _st
{
	int x, y;
};
std::queue<_st> Q;
int visited[500 + 2][500 + 2];

void input()
{
	scanf("%d %d", &R, &C);
	for (int i = 1; i <= R; i++) {
		scanf("%s", &board[i][1]);
		for (int j = 1; j <= C; j++) {
			if (board[i][j] == 'X') visited[i][j] = 1;
		}
	}
	scanf("%d %d", &sx, &sy);
	scanf("%d %d", &ex, &ey);
}


bool BFS()
{
	// dir
	int dir_x[4] = { 0, 0, 1, -1 };
	int dir_y[4] = { 1, -1, 0, 0 };

	Q.push({ sx, sy });
	visited[sx][sy] = 1;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();


		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 1 || nx > R || ny < 1 || ny > C) continue;
			// 현재 칸에서 상태발전 시키려는 곳이 목적 위치인 동시에 이미 방문한 적이 있는 곳이라면 탈출 가능하다. 
			if (nx == ex && ny == ey && visited[nx][ny] == 1) return true;	
			if (board[nx][ny] == 'X') continue;
			if (visited[nx][ny]) continue;
			Q.push({ nx, ny });
			visited[nx][ny] = 1;
		}
	}
	return false;
}



int main()
{
	input();
	if (!BFS()) printf("NO\n");
	else printf("YES\n");
	return 0;
}