백준 16137 견우와 직녀

문제 링크

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

문제

키 포인트

◆ 백준 연구소 문제처럼 오작교를 놓을 수 있는 위치에 오작교를 하나씩 놓아가며 simulation을 돌려본다.

◆ 특히 절벽이 교차하는 지점(ㄱ자 모양)은 오작교를 놓을 수 없으므로 검사가 필요! (절벽인 좌표에서 ㄱ자모양을 시계방향으로 돌려가며 확인)

◆ 각 좌표에는 직전에 오작교를 건넌 경우와 건너지 않은 2가지 경우가 있기 때문에 int dist[11][11][2]로 선언 후 해당 지점까지 걸린 시간을 저장한다.
(연속으로 오작교를 못건너기 때문에)
연속으로 건너는지는 q에 before 를통해 체크가 가능하다.
dist는 그냥 2차원 배열로 선언해서 다시 풀어봤는데 통과됐다.

시행착오

처음에 풀 때는 int dist[11][11] 대신 bool visit[11][11] 배열을 선언후 각 좌표에는 방문 했는지 여부만 표시했다.
그리고 변수 cnt를 두어 q가 돌아가는 주기에 따라 cnt값을 1씩 증가시켜 가며 거리를 측정하려 했다.

그런데 이 방법으로는 오작교 앞에서 가만히 기다리는 경우를 계산하기가 까다로웠다.(q에 x,y좌표를 그대로 남겨둘 수는 없고.. 어떻게 해야하나.. 고민했다)

한참 고민하다 결국 dist 배열을 새로 놓고 풀었다.

코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define INF 2147483647
typedef struct info {
	int x, y;
	bool before;
}info;

int n, m;
int maps[11][11];
int dist[11][11];
int dx[4]{ 0,1,0,-1 };
int dy[4]{ 1,0,-1,0 };
bool can_struct(int x,int y) {
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;

		int nx2 = x + dx[(i + 1) % 4];
		int ny2 = y + dy[(i + 1) % 4];
		if (nx2 < 0 || nx2 >= n || ny < 0 || ny >= n) continue;

		if (maps[nx][ny] == 0 && maps[nx2][ny2] == 0) return false;
	}
	return true;
}

int simulation() {
	queue<info> q;
	fill(&dist[0][0], &dist[10][11], INF);
	q.push({ 0,0,false });
	dist[0][0] = 0;
	int cnt = 0;
	while (!q.empty()) {
		int sz = q.size();
		for(int i=0;i<sz;i++){
			int x = q.front().x;
			int y = q.front().y;
			bool before = q.front().before;
			q.pop();

			

			for (int j = 0; j < 4; j++) {
				int nx = x + dx[j];
				int ny = y + dy[j];
				if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
				if (maps[nx][ny] == 0) continue;
				if (maps[nx][ny] == 1) {
					if (dist[nx][ny] > dist[x][y] + 1) {
						dist[nx][ny] = dist[x][y] + 1;
						q.push({ nx,ny,0 });
					}
				}
				else if (maps[nx][ny] > 1 && !before ) {
					int next = dist[x][y] + maps[nx][ny] - dist[x][y] % maps[nx][ny];
					if (dist[nx][ny]>next) {
						dist[nx][ny] = next;
						q.push({ nx,ny,true });
					}
				}
			}
		}
		cnt++;
	}
	return dist[n - 1][n - 1];
}

int select() {
	int minn = INF;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (maps[i][j] == 0 && can_struct(i, j)) {
				maps[i][j] = m;
				minn = min(minn, simulation());
				maps[i][j] = 0;
			}
		}
	}
	return minn;
}




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 >> maps[i][j];
		}
	}
	cout<<select();
}

추가

BFS 문제를 여러번 접하다보니 어느정도 암기를 해버려서 별생각없이 방향을 잡고 푼게 치명적이었다.
딱딱하게 생각하지 말자. 문제 자체는 그렇게 어렵지 않은거 같은데 내가 너무 바보같다. 나중에 꼭 복습하자