[BOJ] 16137 : 견우와 직녀 - travelbeeee

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

---

[ 주접주접 ]

 단순 BFS 문제 같은데 왜이렇게 정답률이 극악인가했더니,,, 문제를 완벽하게 이해하기가 참 어렵고 숨겨진 조건이 많아서 결국 2번 틀리고 Solve를 받았다.

 

[ 알고리즘풀이 ]

● 견우는 오작교를 연속해서 건널 수 없다! 즉, 오작교가 2개가 연달아있으면 연달아 오작교를 이용할 수 없다.

● 주기가 M인 오작교는 내가 M - 1 시점에 오작교 옆에 땅이여야 M 시점에 오작교로 이동이 가능하다.

● 먼저 오작교를 세울 수 있는 절벽인지 아닌지 판단한 후 세울 수 있다면 bridge에 좌표를 다 담는다.

( 이때, 오작교를 세울 수 있는지 없는지는 왼쪽 + 위 / 위 + 오른쪽 / 오른쪽 + 아래 / 아래 + 왼쪽 이 동시에 절벽인지 아닌지 체크해주면 된다. )

● 오작교를 세우지 않고 BFS 탐색을 진행하고, 그 후 오작교를 세울 수 있는 절벽마다 주기가 M인 오작교를 세운 후 BFS 탐색을 진행한다.

● BFS 탐색은 총 4가지 값들을 queue에 담으면서 진행하는데 << x좌표, y좌표 >, <현재시간, 오작교밟았는지여부>> 를 통해 내가 다음에 밟아야할 좌표가 일반적인땅(1) 이라면 그냥 queue에 <<다음에밟아야할좌표>, <현재시간+1, 0>> 을 push 해주고, 오작교라면 오작교 주기와 맞아떨어져서 밟을 수 있고, 기존에 오작교를 밟지 않았다면 오작교로 이동을 하고, 오작교 주기와 맞아떨어지지않지만 기존에 오작교를 밟지 않았다면 현재 자리에서 대기를 해야되므로 현재 자리를 다시 push 해준다.

#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

int N, M, map[10][10], ans = 99999;
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };

bool checkBound(int i, int j) {
	if (0 <= i && i < N && 0 <= j && j < N)
		return true;
	return false;
}

bool checkBridge(int i, int j) {
	if (checkBound(i, j - 1) && checkBound(i - 1, j) && map[i][j - 1] == 0 && map[i - 1][j] == 0)
		return false;
	if (checkBound(i - 1, j) && checkBound(i, j + 1) && map[i - 1][j] == 0 && map[i][j + 1] == 0)
		return false;
	if (checkBound(i, j + 1) && checkBound(i + 1, j) && map[i][j + 1] == 0 && map[i + 1][j] == 0)
		return false;
	if (checkBound(i + 1, j) && checkBound(i, j - 1) && map[i + 1][j] == 0 && map[i][j - 1] == 0)
		return false;
	return true;
}

void BFS(void) {
	bool visited[10][10] = {};
	queue<pair<pair<int, int>,pair<int, int>>> q;
	q.push({ {0, 0}, {0, 0} });
	visited[0][0] = 1;

	while (!q.empty()) {
		pair<pair<int, int>,pair<int, int>> cur = q.front();
		q.pop();
		pair<int, int> curP = cur.first;
		int time = cur.second.first;
		int flag = cur.second.second;

		if (curP == make_pair(N - 1, N - 1)) {
			ans = min(ans, time);
			break;
		}

		for (int i = 0; i < 4; i++) {
			int nX = curP.first + dx[i], nY = curP.second + dy[i];
			if (!checkBound(nX, nY))
				continue;

			if (map[nX][nY] == 1 && !visited[nX][nY]) { // 그냥 갈 수 있는 땅
				q.push({ {nX,nY}, {time + 1, 0} });
				visited[nX][nY] = 1;
			}

			if (map[nX][nY] >= 2 && !visited[nX][nY] && !flag) { // 오작교가 있고 전에 오작교를 밟지 않음.
				if ((time + 1) % map[nX][nY] == 0) { // 오작교를 갈 수 있다.
					visited[nX][nY] = 1;
					q.push({ {nX, nY}, {time + 1, 1} });
				}
				else { // 제자리 대기
					q.push({ {curP.first, curP.second}, {time + 1, 0} });
				}
			}
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

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

	vector<pair<int, int>> bridge;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 0 && checkBridge(i, j)) {
				bridge.push_back({ i, j });
			}
		}
	}
	
	BFS();
	for (int i = 0; i < bridge.size(); i++) {
		map[bridge[i].first][bridge[i].second] = M;
		BFS();
		map[bridge[i].first][bridge[i].second] = 0;
	}

	cout << ans << '\n';

	return 0;
}

---