[백준 16137] 견우와 직녀 (C++)

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

16137번: 견우와 직녀

1. 주의할 점

- 교차로인 경우 오작교를 짓지 못하도록 한다

- 연속으로 다리를 건널 수 없다

- 1칸씩 이동한다

 

2. 구현

- 맵을 입력 받은 후, 교차로의 경우 좌우/상하 를 확인하여 옆에 칸이 땅이 아닌 경우 +1씩 하여 둘다 1이상을 기록할 경우, 교차로라고 판단 -> Arr[][]의 값을 -1로 변경

- BFS를 통해 구현

- 이동하려는 칸이 땅인 경우, Check[][][]값과 비교하며 이동할 수 있는 경우 tmp.state=0으로 무조건 고정한다(직전에 오작교를 사용하지 않았다는 증거)

- 이동하려는 칸이 교차로인 경우, Continue

- 이동하려는 칸이 0인 경우(주기가 M인 오작교 생성 가능), 이미 주기가 M인 오작교를 생성한 적이 있거나, 직전에 오작교를 건넌 경우 Continue. 이외의 경우 Check[][][]값을 비교하여 이동

- 이동하려는 칸이 2 이상의 값을 지닌 오작교인 경우, 직전에 오작교를 건넌 경우 Continue. 이외의 경우 Check[][][]값을 비교하여 이동

 

#define MAX 987654321
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct info {
	int x, y, state, val, made;
};
info tmp;
int arr[10][10], num, bridge, result;
int check[10][10][2];		//0: 주기가 M인 오작교 아직 안만듬, 1: 만듬
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };

int main() {
	cin >> num >> bridge;
	for (int i = 0; i < num; i++)
		for (int j = 0; j < num; j++) {
			cin >> arr[i][j];
			check[i][j][0] = MAX;
			check[i][j][1] = MAX;
		}
	for (int i = 0; i < num; i++)
		for (int j = 0; j < num; j++) {
			if (arr[i][j] == 0) {
				int r = 0;
				int c = 0;
				for (int k = 0; k < 4; k += 2) {
					int nx = j + dx[k];
					int ny = i + dy[k];
					if (nx >= 0 && ny >= 0 && nx < num && ny < num && arr[ny][nx] != 1)
						r++;
				}
				for (int k = 1; k < 4; k += 2) {
					int nx = j + dx[k];
					int ny = i + dy[k];
					if (nx >= 0 && ny >= 0 && nx < num && ny < num && arr[ny][nx] != 1)
						c++;
				}
				if (c > 0 && r > 0) arr[i][j] = -1;
			}
		}
	result = MAX;
	queue<info> q;
	tmp.x = 0;
	tmp.y = 0;
	tmp.state = 0;
	tmp.val = 0;
	tmp.made = 0;
	q.push(tmp);
	check[0][0][0] = 0;
	while (!q.empty()) {
		int cx = q.front().x;
		int cy = q.front().y;
		int cv = q.front().val;
		int cs = q.front().state;
		int cm = q.front().made;
		q.pop();
		if (cx == num - 1 && cy == num - 1) {
			result = min(result, cv);
			continue;
		}
		for (int k = 0; k < 4; k++) {
			int nx = cx + dx[k];
			int ny = cy + dy[k];
			if (nx >= 0 && ny >= 0 && nx < num && ny < num) {
				if (arr[ny][nx] == 1 && check[ny][nx][cm] > cv + 1) {
					check[ny][nx][cm] = cv + 1;
					tmp.x = nx;
					tmp.y = ny;
					tmp.val = cv + 1;
					tmp.state = 0;
					tmp.made = cm;
					q.push(tmp);
				}
				else if (arr[ny][nx] == -1) continue;	//교차로인 경우
				else if (arr[ny][nx] == 0) {
					if (cm == 1 || cs==1) continue;		//이미 오작교를 하나 만든 경우
					int v = 0;
					if((cv + 1) % bridge != 0)
						v = bridge - (cv + 1) % bridge;
					if (check[ny][nx][1] > cv + v + 1) {
						check[ny][nx][1] = cv + v + 1;
						tmp.x = nx;
						tmp.y = ny;
						tmp.state = 1;
						tmp.val = cv + v + 1;
						tmp.made = 1;
						q.push(tmp);
					}
				}
				else if (arr[ny][nx] > 1) {
					//방금 오작교를 건넜거나, 아직 오작교가 쉬는 중인 경우
					if (cs == 1) 	continue;					
					int v = 0;
					if ((cv + 1) % arr[ny][nx] != 0)
						v = arr[ny][nx] - (cv + 1) % arr[ny][nx];
					if (check[ny][nx][1] > cv + v + 1) {
						check[ny][nx][1] = cv + v + 1;
						tmp.x = nx;
						tmp.y = ny;
						tmp.state = 1;
						tmp.val = cv + v + 1;
						tmp.made = cm;
						q.push(tmp);
					}
				}
			}
		}
	}
	cout << result << '\n';
	system("pause");
	return 0;
}