[BOJ/Gold 2] 백준 16137 견우와 직녀(C++)

문제 링크

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

16137번: 견우와 직녀

문제

견우와 직녀는 여러 섬과 절벽으로 이루어진 지역에서 살고 있다. 이 지역은 격자로 나타낼 수 있으며, 상하좌우로 인접한 칸으로 가는 데 1분이 걸린다.

7월 7일은 견우와 직녀가 오작교를 건너 만날 수 있는 날이다. 그런데 고령화로 인해서 까마귀와 까치가 예전처럼 커다란 오작교를 만들 수 없다. 그래서 요즘은 일부 절벽에만 다리를 만들어 주고 있고, 그마저도 힘들어서 몇 분 주기로 오작교를 짓고 해체하는 작업을 반복해야 한다. 한 번 지은 오작교는 1분 동안 유지할 수 있다.

예를 들어 오작교가 3분과 4분 주기라면, 건널 수 있는 시간은 아래 그림에서 초록색으로 표시한 부분과 같다.

까마귀와 까치는 조금이라도 견우를 더 도와주기 위해, 절벽을 정확히 하나 골라 주기가 M분인 오작교를 하나 더 놓아 주기로 했다. 단, 이미 오작교를 짓기로 예정한 절벽에는 오작교를 하나 더 놓을 수 없고, 아래와 같이 절벽이 가로와 세로로 교차하는 곳에도 오작교를 놓을 수 없다.오작교는 이처럼 매우 불안정하므로, 견우는 안전을 위해 두 번 연속으로 오작교를 건너지는 않기로 했다.

아래 그림에서 파란색은 견우가 건널 수 있는 일반적인 땅, 검은색은 절벽, 흰색은 절벽이 교차해서 오작교를 놓을 수 없는 위치를 나타낸다.

견우가 직녀에게 도착할 수 있는 최소의 시간을 찾아 보자.

입력

첫째 줄에 지형의 행과 열의 크기를 나타내는 정수 N (2 ≤ N ≤ 10)과 새로 만들어지는 오작교의 주기를 의미하는 정수 M(2 ≤ M ≤ 20)이 주어진다.

다음 N개의 줄에는 줄마다 배열의 각 행을 나타내는 N개의 정수가 한 개의 빈칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 20 이하이다.

또한, 각 칸에 들어가는 정수의 의미는 다음과 같다.

• 1: 이동할 수 있는 일반적인 땅
• 0: 건널 수 없는 절벽
• 2 이상의 수: 적혀있는 수 만큼의 주기를 가지는 오작교

견우의 시작점은 지형의 맨 왼쪽 위 (0, 0) 이고, 직녀가 사는 곳은 지형의 맨 오른쪽 아래인 (N-1, N-1)이다. 견우가 시작점에서 출발하는 시간은 0분이다. 견우와 직녀가 사는 곳은 일반적인 땅이다.

견우와 직녀가 무조건 만날 수 있는 경우만 주어진다. 또한, 주어지는 지형 정보에서 오작교를 반드시 하나 이상 놓을 수 있다. 절벽이 가로와 세로로 교차하는 지점에는 오작교가 설치되어 있지 않다.

출력

견우가 직녀에게 갈 수 있는 최소의 시간을 출력한다.

예제 입력 1

5 5
1 1 1 1 1
0 6 0 0 0
1 1 0 1 1
1 1 0 1 1
1 1 0 1 1

예제 출력 1

8

알고리즘 분류

• 구현
• 그래프 탐색
• 브루트포스 알고리즘

풀이

이해하는 것부터 어려운 문제였으니 평소에 유튜브 보지 말고 책을 열심히 읽도록 하자.

우선 절벽들은 가로 절벽과 세로 절벽의 교차점인지를 따져서 교차점이라면 -1로 초기화시킨다.

그리고 처음에 BFS를 한 번 실행하여 견우가 직녀에게 도달하는 데 걸리는 시간을 구한다.

그리고 절벽(0)인 칸마다 주기가 M인 오작교를 놓는다.(MAP[][] = M) 놓은 후에 다시 BFS를 실행하여 견우가 직녀에게 도달하는 데 걸리는 시간을 구한다.

많아 봤자 10X10=100칸이며, 거기에 견우가 직녀에게 반드시 도달할 수 있는 경우만 주어진다고 하였으므로 실제로 오작교를 놓을 수 있는 절벽은 100칸보다는 훨씬 줄어들기 때문에 시간 초과에 걸리지 않는다.

BFS를 실행할 때에는 다음 칸이 일반적인 땅(1)이라면 건너고, 다음 칸이 오작교(2 이상)라면 건널 수 있는지 파악한다. 만약에 건널 수 있는 시간이라면 현재 칸이 일반적인 땅인지 아니면 오작교인지를 따진다. 오작교라면, 견우가 오작교를 연속으로 건널 수 없다고 하였으므로 건너지 않으며, 일반적인 땅이라면 오작교를 건넌다. 오작교를 건널 수 없는 시간이라면 시간만 1 증가시키고 같은 칸에 머문다.

이렇게 오작교를 놓지 않았을 때와 오작교를 각 절벽에 놓았을 때 BFS를 각각 실행해서 얻은 최소 이동 거리를 구한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 10
#define LL long long
#define INF 2e9

using namespace std;
int N, M;
int MAP[MAX][MAX];
bool visited[MAX][MAX];
int moveY[4] = { -1,0,1,0 };
int moveX[4] = { 0,-1,0,1 };
int answer = INF;

void init() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			visited[i][j] = false;
		}
	}
}

void Crossroad(int Y, int X) {
	int CntR = 0;
	int CntC = 0;
	for (int i = 0; i < 4; i++) {
		if (i % 2 == 0) {
			int nextY = Y + moveY[i];
			int nextX = X + moveX[i];
			if ((nextY >= 0) && (nextY < N) && (nextX >= 0) && (nextX < N) && (MAP[nextY][nextX] == 0)) {
				CntR++;
			}
		}
		else {
			int nextY = Y + moveY[i];
			int nextX = X + moveX[i];
			if ((nextY >= 0) && (nextY < N) && (nextX >= 0) && (nextX < N) && (MAP[nextY][nextX] == 0)) {
				CntC++;
			}
		}
	}
	if ((CntR >= 1) && (CntC >= 1)) {
		MAP[Y][X] = -1;
	}
}

void BFS() {
	init();
	queue<pair<pair<int, int>, int> > Q;
	visited[0][0] = true;
	Q.push(make_pair(make_pair(0, 0), 0));

	while (!Q.empty()) {
		int CurY = Q.front().first.first;
		int CurX = Q.front().first.second;
		int CurT = Q.front().second;
		Q.pop();

		if ((CurY == N - 1) && (CurX == N - 1)) {
			answer = min(answer, CurT);
			return;
		}

		for (int i = 0; i < 4; i++) {
			int nextY = CurY + moveY[i];
			int nextX = CurX + moveX[i];
			if ((nextY >= 0) && (nextY < N) && (nextX >= 0) && (nextX < N) && (!visited[nextY][nextX])) {
				if (MAP[nextY][nextX] == 1) {
					visited[nextY][nextX] = true;
					Q.push(make_pair(make_pair(nextY, nextX), CurT + 1));
				}
				else if (MAP[nextY][nextX] > 1) {
					if ((CurT + 1) % MAP[nextY][nextX] == 0) {
						if (MAP[CurY][CurX] == 1) {
							visited[nextY][nextX] = true;
							Q.push(make_pair(make_pair(nextY, nextX), CurT + 1));
						}
					}
					else {
						Q.push(make_pair(make_pair(CurY, CurX), CurT + 1));
					}
				}
			}
		}
	};
}

int main() {
	FIRST
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> MAP[i][j];
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (MAP[i][j] == 0) {
				Crossroad(i, j);
			}
		}
	}
	BFS();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (MAP[i][j] == 0) {
				MAP[i][j] = M;
				BFS();
				MAP[i][j] = 0;
			}
		}
	}
	cout << answer << "\n";

	return 0;
}