[백준] 1445 - 일요일 아침의 데이트

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

1445번: 일요일 아침의 데이트

 

이 문제의 난이도가 골드 2로 측정된 이유는 국어 능력 때문이라고 생각한다..

1. 쓰레기가 있는 칸('g')은 인접한 칸에 쓰레기가 있던 없던 상관하지 않는다.
2. 즉, 인접한 칸에 쓰레기가 있는 칸을 판단하려면 해당 칸에 아무것도 없어야('.')한다.

그래서 쓰레기 칸인지 판단하는 isGarbage()와 인접한 칸에 쓰레기가 있는지 판단하는 isAdjecant()를 작성하였다.

 

다음은 자료구조 정의이다. 다익스트라에 사용되는 우선순위 큐의 자료구조는 다음과 같이 설정했다.

pair<pair<int, int>, pair<int, int>> -> pair<pair<현재 위치까지 올 때 거친 최소 쓰레기 칸 수, 현재 위치까지 올 때 거친 최소 쓰레기 인접 칸 수>, pair<현재 x좌표, 현재 y좌표>>

사실 구조체로 정의하면 좀 깔끔하게 적을 수 있었지만, 너무 귀찮은 관계로 그러지 않았다.

이 때문에 first.first, second.first 등 알기 어려운 코드를 많이 작성했고 다음부턴 구조체로 작성해야겠다는 마음을 먹었다.

 

이후로는 이다익스트라를 돌려주면 된다.

그런데 현재 칸에서 다음 칸으로 이동하는 경우는 어떤 경우가 있을까?

문제에서 알 수 있는데 바로,

현재 칸까지 거친 최소 쓰레기 칸 수 < 이동할 칸까지 거친 최소 쓰레기 칸 수 또는, 

현재 칸까지 거친 최소 쓰레기 칸 수와 이동할 칸까지 거친 최소 쓰레기 칸 수가 같으며, 현재 칸까지 거친 최소 쓰레기 인접 칸 수 < 이동할 칸까지 거친 최소 쓰레기 인접 칸 수이다.

말로 적으니 매우 이해하기 어렵다. 코드를 보고 이해해보도록 하자.

 

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

char map[50][50];
int n, m;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
pair<int, int> dis[50][50];

struct compare
{
	bool operator()(pair<pair<int, int>, pair<int, int>> &p1, pair<pair<int, int>, pair<int, int>> &p2)
	{
		if (p1.first.first == p2.first.first)
		{
			return p1.first.second > p2.first.second;
		}
		return p1.first.first > p2.first.first;
	}
};

bool isGarbage(pair<int, int> p)
{
	return map[p.first][p.second] == 'g';
}

bool isAdjecant(pair<int, int> p)
{
	if (map[p.first][p.second] != '.')
	{
		return false;
	}
	for (int i = 0; i < 4; i++)
	{
		int nx = p.first + dx[i];
		int ny = p.second + dy[i];
		if (nx >= 0 && nx < n && ny >= 0 && ny < m && map[nx][ny] == 'g')
		{
			return true;
		}
	}
	return false;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	int startx, starty, endx, endy;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 'S')
			{
				startx = i;
				starty = j;
			}
			if (map[i][j] == 'F')
			{
				endx = i;
				endy = j;
			}
			dis[i][j].first = dis[i][j].second = 987654321;
		}
	}

	priority_queue<pair<pair<int, int>, pair<int, int>>, vector<pair<pair<int, int>, pair<int, int>>>, compare> pq;
	pq.push({{0, 0}, {startx, starty}});
	dis[startx][starty] = {0, 0};

	while (!pq.empty())
	{
		int cost1 = pq.top().first.first;
		int cost2 = pq.top().first.second;
		int x = pq.top().second.first;
		int y = pq.top().second.second;
		pq.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			bool gc = isGarbage({nx, ny});
			bool ac = isAdjecant({nx, ny});
			if (nx >= 0 && nx < n && ny >= 0 && ny < m)
			{
				int newCost = cost1 + (gc ? 1 : 0);
				int newCost2 = cost2 + (ac ? 1 : 0);
				if (newCost < dis[nx][ny].first || ((newCost == dis[nx][ny].first && newCost2 < dis[nx][ny].second)))
				{
					pq.push({{newCost, newCost2}, {nx, ny}});
					dis[nx][ny] = {newCost, newCost2};
				}
			}
		}
	}

	cout << dis[endx][endy].first << ' ' << dis[endx][endy].second;
}