[C++]백준 16137번 : 견우와 직녀

www.acmicpc.net/problem/16137

16137번: 견우와 직녀

1. 접근

일단 목적지까지의 최소 도달 시간을 구하는 것이기 때문에 priority queue를 사용한 bfs를 해야겠다고 생각했다.

구현 과정에서 여러 조건들을 맞춰야했다.

 

2. 풀이 과정

이 문제만의 조건과 그에 따른 처리는 다음과 같이 생각했다.

 

1) 목적지로 가는 과정에서 딱 한번 M주기의 다리를 만들어 건널 수 있다.

check[N][N][2]를 통해 check[][][0]은 다리를 만들어 건넌 경우, check[][][1]은 다리를 아직 안만든 경우 map[][]에 도달한 것을 check한다.

이 때 priority queue를 쓰기 때문에 다리를 만들었거나 아직 안 만든 두 경우로만 나누어 제일 빨리 check되는 time만 다루면 된다는 것은 자명하다.

 

2) 절벽 혹은 오작교를 2번 연속으로 건널 수 없다.

즉, 일반적인 땅이 아닌 지형을 2번 연속으로 건널 수 없다는 것이다.

이에 따라 이번 지형이 일반적인 땅이 아닌 경우, 다음 지형 역시 일반적인 땅이 아닐 경우에 탐색을 진행하지 못하도록 조건을 사용했다.

 

3) 절벽이 가로,세로로 교차하는 곳은 오작교를 놓을 수 없다.

해당 조건은 2)번 조건을 만들면서 자동적으로 커버되는 것이 당연한 줄 알았으나 그렇지 않았다.

ㄱ자로 절벽이 이루어진 곳을 생각하면 된다.

교차하는 곳을 -1로 초기화한 후 이에 따라 오작교를 놓을 수 없도록 조건을 추가하니 정답이 되었다.

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <climits>

using namespace std;

struct state{
	int y, x, t, m;
};

struct comp{
	bool operator()(state a, state b){
		return a.t > b.t;
	}
};

int N, M, map[10][10];
priority_queue<state, vector<state>, comp> pq;
bool check[10][10][2] = { false, };
pair<int, int> dir[4] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
int ans = INT_MAX;

void bfs(){
	// init
	pq.push({ 0, 0, 0, 1 });
	for (int i = 0; i < 2; i++)
		check[0][0][i] = true;

	// search
	while (!pq.empty()){
		state s = pq.top();
		pq.pop();

		if (s.y == N - 1 && s.x == N - 1){
			if (ans > s.t)
				ans = s.t;
			continue;
		}

		for (int i = 0; i < 4; i++){
			int ny = s.y + dir[i].first, nx = s.x + dir[i].second;

			if (ny < 0 || ny >= N || nx < 0 || nx >= N)
				continue;

			if (map[ny][nx] == -1)
				continue;

			if (map[ny][nx] == 1 && !check[ny][nx][s.m]){ // just go
				pq.push({ ny, nx, s.t + 1, s.m });
				check[ny][nx][s.m] = true;
			}
			else if (map[ny][nx] == 0 && !check[ny][nx][0]){ // make new bridge
				if (s.m == 0 || map[s.y][s.x] != 1) // 절벽인데 (이미 오작교를 만들었거나 || 바로 이전에도 절벽(오작교)일 때)
					continue;

				int nt = 0;
				while (nt < s.t + 1)
					nt += M;

				pq.push({ ny, nx, nt, 0 });
				check[ny][nx][0] = true;
			}
			else if (map[ny][nx] > 1 && !check[ny][nx][s.m]){ // cross the bridge
				if (map[s.y][s.x] != 1) // 바로 이전에도 절벽(오작교)일때
					continue;

				int nt = map[ny][nx];
				while (nt < s.t + 1)
					nt += map[ny][nx];

				pq.push({ ny, nx, nt, s.m });
				check[ny][nx][s.m] = true;
			}
		}
	}
	return;
}

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> map[i][j];

	// mark map where can't be built bridge
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++){
			if (map[i][j] == 0){
				bool ver = false, hor = false;
				for (int k = 0; k < 2; k++){
					int y = i + dir[k].first, x = j + dir[k].second;

					if ((y >= 0 && y < N&&x >= 0 && x < N) && map[y][x] != 1){
						hor = true;
						break;
					}
				}
				for (int k = 2; k < 4; k++){
					int y = i + dir[k].first, x = j + dir[k].second;

					if ((y >= 0 && y < N&&x >= 0 && x < N) && map[y][x] != 1){
						ver = true;
						break;
					}
				}

				if (ver&&hor)
					map[i][j] = -1;
			}
		}

	bfs();

	cout << ans;

	return 0;
}