백준 15944: 성공

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

 

이 문제는 예전에 푼 문제지만, 내가 직접 풀이를 생각했고, 아이디어가 재밌어서 지금도 기억이 나는 문제이기에, 이번에 다뤄보려고 한다.

 

이 문제를 처음 봤을 때는 Bruteforce 내지 Backtracking이 생각이 난다. 하지만, N과 M이 각각 500이라서 이것을 전부 Backtracking을 하려면 시간이 엄청 오래걸릴 것이다.

 

그럼 어떻게 해야할까? 일단 BFS를 사용하고, 장애물에 막히면 이 장애물을 폭파시키는 방식은 어떨까?

그럼 어딜 폭발시키지? 마주한 장애물을 부수는 경우에 수도 여러가지인데, 이것도 Backtracking을 할것인가?

만약 중간에 폭탄을 터트리는 경우가 최소 폭파의 횟수면 어떡하지?

 

이런저런 생각을 했고, 답이 보이지 않아서 포기할 쯤에, 문득 이런 생각이 들었다.

"특정 장소를 폭파했을 때, 갈 수 있는 장소는 어디일까?"

그러자 이런 생각이 들었다. 폭파란 단어에 매달리지 말자고. 즉, 폭파가 아닌 텔레포트라고 생각을 해보자는 것이다. 지금까지 최단 거리 문제를 풀며 순간이동을 하는 문제는 몇 번이고 맞딱드렸다. 만약 이러한 변환이 가능하다면 이 문제는 처음보게 된 어려운 문제가 아닌 익숙하게 쉬운 문제가 되어버린다. 즉, K가 3일 때, 텔레포트 할 수 있는 범위는 다음과 같다.

빨간색이 텔레포트 범위

그러면 이제 이러한 아이디어를 바탕으로 문제를 해결해보자.

 

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

const int INF = 1000000007;
int N, M, D, ans = 0;
char P[501][501];
int v[501][501];
int dy[4] = { -1 , 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };
vector<int> dy2, dx2;
bool inRange(int y, int x)
{
	return y >= 0 && x >= 0 && y < N&& x < M;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M >> D;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
		{
			cin >> P[i][j];
			v[i][j] = INF;
		}
	for(int i = -D; i <= D; i++)
		for (int j = -D; j <= D; j++)
		{
			if (abs(i) == abs(j) && abs(i) == D) continue;
			dy2.push_back(i); dx2.push_back(j);
		}
	v[0][0] = 0;
	priority_queue<pair<int, pair<int, int>>> pq;
	pq.push({ 0, {0, 0} });
	while (!pq.empty())
	{
		int cost = -pq.top().first;
		int y = pq.top().second.first;
		int x = pq.top().second.second;
		pq.pop();
		if (v[y][x] < cost) continue;
		if (y == N - 1 && x == M - 1)
		{
			ans = v[y][x];
			break;
		}
		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (!inRange(ny, nx) || v[ny][nx] <= cost || P[ny][nx] == '#') continue;
			v[ny][nx] = cost;
			pq.push({-cost, {ny, nx} });
		}
		for (int i = 0; i < dx2.size(); i++)
		{
			int ny = y + dy2[i];
			int nx = x + dx2[i];
			if (!inRange(ny, nx) || v[ny][nx] <= cost + 1) continue;
			v[ny][nx] = cost + 1;
			pq.push({ -(cost + 1), {ny, nx} });
		}
	}
	cout << ans << '\n';
}

결과는? "시간초과"이다.

 

뭐가 문제일까? 텔레포트 범위가 너무 넓다. 이것을 줄여야한다. 여기서 목적지가 끝자락에 있다는 것에 주목해야한다. 즉, 폭파범위의 주위만 계산해도 충분하다는 것을 인지했어야했다. 따라서 텔레포트 범위를 다음과 같이 수정을 해야한다.

이제 코드를 수정하면 다음과 같다.

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

const int INF = 1000000007;
int N, M, D, ans = 0;
char P[501][501];
int v[501][501];
int dy[4] = { -1 , 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };
vector<int> dy2, dx2;
bool inRange(int y, int x)
{
	return y >= 0 && x >= 0 && y < N&& x < M;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M >> D;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
		{
			cin >> P[i][j];
			v[i][j] = INF;
		}
	for(int i = -D; i <= D; i++)
		for (int j = -D; j <= D; j++)
		{
			if (abs(i) == abs(j) && abs(i) == D) continue;
			if (abs(i) != D && abs(j) != D && abs(i) != 0 && abs(j) != 0) continue; // 추가 된 부분
			dy2.push_back(i); dx2.push_back(j);
		}
	v[0][0] = 0;
	priority_queue<pair<int, pair<int, int>>> pq;
	pq.push({ 0, {0, 0} });
	while (!pq.empty())
	{
		int cost = -pq.top().first;
		int y = pq.top().second.first;
		int x = pq.top().second.second;
		pq.pop();
		if (v[y][x] < cost) continue;
		if (y == N - 1 && x == M - 1)
		{
			ans = v[y][x];
			break;
		}
		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (!inRange(ny, nx) || v[ny][nx] <= cost || P[ny][nx] == '#') continue;
			v[ny][nx] = cost;
			pq.push({-cost, {ny, nx} });
		}
		for (int i = 0; i < dx2.size(); i++)
		{
			int ny = y + dy2[i];
			int nx = x + dx2[i];
			if (!inRange(ny, nx) || v[ny][nx] <= cost + 1) continue;
			v[ny][nx] = cost + 1;
			pq.push({ -(cost + 1), {ny, nx} });
		}
	}
	cout << ans << '\n';
}

폭파 범위의 둘레만 텔레포트 하도록 수정하였다. 이제 결과는? "시간 초과"는 아니다. 하지만 "틀렸습니다"이다.

 

이젠 뭐가 틀렸다는것인가? 여기까지 오는 것도 힘들었는데, 더 고민을 해야한다니... 그 때, 반례가 하나 떠올랐다.

둘레가 범위를 벗어날 경우, 답을 어떻게 구할 것이냐? 이다. 이전의 아이디어는 모든 텔레포트 범위를 전부 탐색을 해서 이러한 것을 고민을 이유가 없었다. 그런데, 둘레로 변환하니, 둘레 안에 목적지가 있을 경우 이 목적지에 도달하지 못하는 경우가 생긴 것이다. 그렇다면? 텔레포트 범위가 밖을 벗어날 경우 격자 안 쪽으로 텔레포트 범위를 수정해야한다.

 

어떻게 격자 안쪽으로 옮겨야할까? 이 때, Clamp 방식을 사용하기로 한다. 범위 밖을 벗어나는 값을 범위의 최대 혹은 최소 값으로 변환하는 것이다. 나는 이것을 min, max 함수를 사용해서 구현을 했다.

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

const int INF = 1000000007;
int N, M, D, ans = 0;
char P[501][501];
int v[501][501];
int dy[4] = { -1 , 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };
vector<int> dy2, dx2;
bool inRange(int y, int x)
{
	return y >= 0 && x >= 0 && y < N&& x < M;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M >> D;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
		{
			cin >> P[i][j];
			v[i][j] = INF;
		}
	for (int i = -D; i <= D; i++)
		for (int j = -D; j <= D; j++)
		{
			if (abs(i) == abs(j) && abs(i) == D) continue;
			if (abs(i) != D && abs(j) != D && abs(i) != 0 && abs(j) != 0) continue;
			dy2.push_back(i); dx2.push_back(j);
		}
	v[0][0] = 0;
	priority_queue<pair<int, pair<int, int>>> pq;
	pq.push({ 0, {0, 0} });
	while (!pq.empty())
	{
		int cost = -pq.top().first;
		int y = pq.top().second.first;
		int x = pq.top().second.second;
		pq.pop();
		if (v[y][x] < cost) continue;
		if (y == N - 1 && x == M - 1)
		{
			ans = v[y][x];
			break;
		}
		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (!inRange(ny, nx) || v[ny][nx] <= cost || P[ny][nx] == '#') continue;
			v[ny][nx] = cost;
			pq.push({ -cost, {ny, nx} });
		}
		for (int i = 0; i < dx2.size(); i++)
		{
			int ny = max(0, min(N - 1, y + dy2[i])); // Clamp 추가
			int nx = max(0, min(M - 1, x + dx2[i])); // Clamp 추가
			if (v[ny][nx] <= cost + 1) continue;
			v[ny][nx] = cost + 1;
			pq.push({ -(cost + 1), {ny, nx} });
		}
	}
	cout << ans << '\n';
}

 

결과는? 이제야 "맞았습니다"를 얻는다. 티어는 플레티넘 2, 아이디어가 재밌었던 문제였다.