[BOJ] 16137 견우와 직녀

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

 

<조건>

• 두 번 연속으로 오작교를 건너지는 않기
  • 2 이상의 수는 모두 오작교임을 명심하자
• 절벽을 정확히 하나 골라 주기가 M분인 오작교를 하나 더 놓아 줌
• 절벽이 가로와 세로로 교차하는 곳에 오작교를 놓을 수 없다.

 

문제 풀이:

• bfs를 이용해 문제를 해결하였다.
• 오작교의 주기인 M이 20 이하이기 때문에, 건널 수 있는 시간이 되지 않았다면 그 자리에서 기다리도록 하였다.
• visit 체크는 현재 위치(x, y)와 오작교를 설치 여부를 고려하였다.
• 이 문제의 핵심은 조건을 잘 이해하는 것!!

 

소스 코드:

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;


int n, m, arr[11][11], answer;
bool visit[11][11][2];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };

struct state {
	int x;
	int y;
	int  time;
	bool build;
	bool bridge;
};
int func() {

	queue<state> q;
	q.push({ 0,0,0,false,false });
	visit[0][0][0] = true;

	while (!q.empty()) {
		int curX = q.front().x;
		int curY = q.front().y;
		int curTime = q.front().time + 1;
		bool build = q.front().build;
		bool bridge = q.front().bridge;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int x = curX + dx[i];
			int y = curY + dy[i];
			bool newBuild = build;
			bool newBridge = bridge;
			if (x < 0 || x >= n || y < 0 || y >= n) continue;

			if (visit[x][y][newBuild]) continue;

			int t = arr[x][y];
			if (t == 0) {
				if (newBuild || newBridge) continue;
				else if (x - 1 >= 0 && y - 1 >= 0 && arr[x - 1][y] == 0 && arr[x][y - 1]==0) continue;
				else if (y + 1 < n && x + 1 < n && arr[x][y + 1] == 0 && arr[x + 1][y]==0) continue;
				else if (x - 1 >= 0 && y + 1 < n && arr[x-1][y] == 0 && arr[x][y+1] == 0) continue;
				else if (x +1 <n && y - 1 >= 0 && arr[x +1][y] == 0 && arr[x][y - 1]==0) continue;

				if (curTime % m == 0) {
					visit[x][y][newBuild] = true;
					if (x == n - 1 && y == n - 1) return curTime;

					newBridge = true;
					q.push({ x,y,curTime,true,true });
				}
				else {
					q.push({ curX,curY,curTime,newBuild,newBridge });
				}
				continue;
			}
			else if (t > 1 && newBridge) {
				continue;
			}

			if (curTime % t == 0) {
				visit[x][y][newBuild] = true;
				if (x == n - 1 && y == n - 1) return curTime;

				if (t == 1) newBridge = false;
				else newBridge = true;
				q.push({ x,y,curTime,newBuild,newBridge });
			}
			else {
				q.push({ curX,curY,curTime,newBuild,newBridge });
			}

		}
	}

	return 0;
}

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

	cin >> n >> m;

	answer = 20 * n * n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}

	cout << func() << '\n';
	return 0;
}