[BOJ] 16137. 견우와 직녀

문제 원본 : https://www.acmicpc.net/problem/16137

16137번: 견우와 직녀

#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<string>
#include<map>
#include<algorithm>

using namespace std;

int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;

	vector<vector<int> > map(N, vector<int>(N, 0));
	vector<vector<int> > tmp(N, vector<int>(N, 0));
	vector<pair<int, int> > bridge;
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
		{
			cin >> map[i][j];
			if (map[i][j] == 0)
				bridge.push_back(make_pair(i, j));
		}

	priority_queue<pair<int, pair<int, int> > > q;
	int ans = 1234567890;
	for (int i = 0; i < bridge.size(); ++i)
	{
		int chk = 0;
		for (int k = 3; k >= 0; --k)
		{
			chk <<= 1;
			int ni = bridge[i].first + dir[k][0];
			int nj = bridge[i].second + dir[k][1];
			if (ni < 0 || ni >= N || nj < 0 || nj >= N || map[ni][nj] > 1)
				continue;
			
			if (map[ni][nj] == 0)
				chk |= 1;
		}
		if (chk == 15 || chk == 14 || chk == 13 || chk == 11 || chk == 7 || chk == 12 || chk == 6 || chk == 3 || chk == 9)
			continue;

		vector<vector<int> > time(N, vector<int>(N, 1234567890));
		tmp = map;
		tmp[bridge[i].first][bridge[i].second] = M;
		q.push(make_pair(0, make_pair(0, 0)));
		time[0][0] = 0;
		while (!q.empty())
		{
			int cy = q.top().second.first;
			int cx = q.top().second.second;
			int ct = -q.top().first;
			q.pop();
			if (ct > time[cy][cx])
				continue;

			for (int j = 0; j < 4; ++j)
			{
				int ny = cy + dir[j][0];
				int nx = cx + dir[j][1];
				if (ny < 0 || ny >= N || nx < 0 || nx >= N || tmp[ny][nx] == 0)
					continue;
				if (tmp[cy][cx] > 1 && tmp[ny][nx] > 1)
					continue;
				if (tmp[ny][nx] == 1 && time[ny][nx] > time[cy][cx] + 1)
				{
					time[ny][nx] = time[cy][cx] + 1;
					q.push(make_pair(-time[ny][nx], make_pair(ny, nx)));
				}
				else if (tmp[ny][nx] > 1 && time[ny][nx] > time[cy][cx] + tmp[ny][nx] - time[cy][cx] % tmp[ny][nx])
				{
					time[ny][nx] = time[cy][cx] + tmp[ny][nx] - time[cy][cx] % tmp[ny][nx];
					q.push(make_pair(-time[ny][nx], make_pair(ny, nx)));
				}
			}
		}
		if (ans > time[N - 1][N - 1])
			ans = time[N - 1][N - 1];
	}
	cout << ans << "\n";
}

• 너비 우선 탐색과 완전 탐색을 합쳐 놓은 느낌의 문제.
• 우선 번호가 0인 곳에만 오작교를 설치할 수 있으므로 0인 좌표의 리스트를 만든다.
• 그리고 비트 연산을 이용해 절벽이 교차하는 곳을 체크해서 건너뛴다.
• 우선순위 큐를 이용해 나머지 오작교 설치 가능 한 곳을 전부 계산.