백준 23268: Deceptive Directions

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

 

이 문제의 초기 아이디어는 어렵지 않았다. BFS의 층수에 따라, 명령을 매칭해서, 해당 명령과 다른 곳으로 옮길 수 있을 때 옮긴다는 아이디어였다. 그렇게 나온 코드는 다음과 같다.

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;

int W, H, sy = 0, sx = 0;
char M[1001][1001];
bool v[1001][1001];
string D;
vector<int> input;
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> W >> H;
	for (int i = 0; i < H; i++)
		for (int j = 0; j < W; j++)
		{
			cin >> M[i][j];
			if (M[i][j] == 'S')
			{
				sy = i;
				sx = j;
			}
		}
	cin >> D;
	for (int i = 0; i < D.size(); i++)
	{
		switch (D[i])
		{
		case 'N':
			input.push_back(0);
			break;
		case 'S':
			input.push_back(1);
			break;
		case 'W':
			input.push_back(2);
			break;
		default:
			input.push_back(3);
			break;
		}
	}
	queue<pair<int, int>> q;
	q.push({ sy, sx });
	v[sy][sx] = true;
	for (int i = 0; i < input.size(); i++)
	{
		int s = q.size();
		while (s--) 
		{
			int y = q.front().first;
			int x = q.front().second;
			q.pop();
			for (int d = 0; d < 4; d++)
			{
				if (input[i] == d) continue;
				int ny = y + dy[d];
				int nx = x + dx[d];
				if (ny < 0 || nx < 0 || ny >= H || nx >= W || v[ny][nx] || M[ny][nx] == '#') continue;
				v[ny][nx] = true;
				q.push({ ny, nx });
			}
		}
	}
	while (!q.empty())
	{
		int y = q.front().first;
		int x = q.front().second;
		M[y][x] = '!';
		q.pop();
	}
	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
			cout << M[i][j];
		cout << '\n';
	}
}

이 코드가 답일것이라 기대했지만, 내가 마주한것은 "틀렸습니다"였다.

반례를 만들어서, 코드의 문제점을 찾고 싶었는데, 직접 예시를 만들기 애매하고, 이 문제를 해결한 사람자체가 적어서 질문 게시판은 비었었다. 결국 이 문제를 출처의 데이터를 찾아서, 손수 입력을 한 결과, 문제점을 알게 되었다.

 

there is no shorter way of reaching the treasure(보물에 도달하는 데 명령보다 작은 길은 없다)

이 문장을 잘 살폈어야했다. 즉, 보물이 있을 가능성이 있는 곳은 최단 거리이다, 해당 위치에 도달했을 때, 거리가 최단 거리보다 크다면 표시를 하지 말하야한다.

 

이것을 위해 미리 BFS로 최단거리를 구하고, 다시 BFS를 돌며 비교하면 된다.

#include <iostream>
#include <queue>
#include <cmath>
#include <cstring>

using namespace std;

int W, H, sy = 0, sx = 0;
char M[1001][1001];
int v[1001][1001];
string D;
vector<int> input;
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };
bool inRange(int y, int x)
{
	return y >= 0 && x >= 0 && y < H && x < W;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	memset(v, -1, sizeof(v));
	cin >> W >> H;
	for (int i = 0; i < H; i++)
		for (int j = 0; j < W; j++)
		{
			cin >> M[i][j];
			if (M[i][j] == 'S')
			{
				sy = i;
				sx = j;
			}
		}
	cin >> D;
	for (int i = 0; i < D.size(); i++)
	{
		switch (D[i])
		{
		case 'N':
			input.push_back(0);
			break;
		case 'S':
			input.push_back(1);
			break;
		case 'W':
			input.push_back(2);
			break;
		default:
			input.push_back(3);
			break;
		}
	}
	queue<pair<int, int>> q;
	q.push({ sy, sx });
	v[sy][sx] = 0;
	while (!q.empty())
	{
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int d = 0; d < 4; d++)
		{
			int ny = y + dy[d];
			int nx = x + dx[d];
			if (!inRange(ny, nx) || v[ny][nx] >= 0 || M[ny][nx] == '#') continue;
			v[ny][nx] = v[y][x] + 1;
			q.push({ ny, nx });
		}
	}
	q.push({ sy, sx });
	for (int i = 0; i < input.size(); i++)
	{
		int s = q.size();
		while (s--)
		{
			int y = q.front().first;
			int x = q.front().second;
			q.pop();
			for (int d = 0; d < 4; d++)
			{
				if (input[i] == d) continue;
				int ny = y + dy[d];
				int nx = x + dx[d];
				if (!inRange(ny, nx) || M[ny][nx] == '#' || v[ny][nx] < 0 || v[ny][nx] != i + 1) continue;
				v[ny][nx] = true;
				q.push({ ny, nx });
			}
		}
	}
	while (!q.empty())
	{
		int y = q.front().first;
		int x = q.front().second;
		M[y][x] = '!';
		q.pop();
	}
	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
			cout << M[i][j];
		cout << '\n';
	}
}

기존에 중복 방지를 위해 사용한 v 배열을 최단거리 배열로 대체하였다.

아무 생각없이 넘어간 문장이 이렇게 큰 문제가 될 줄은 몰랐다. 영어라서 대강 해석했기에 이런 사태를 불러온 것 같은데, 외국어라도, 좀 더 천천히 읽어보도록하자.