백준 2151번 거울 설치

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

2151번: 거울 설치

 

 

 

 

 

 

<접근방법>

완전 탐색 문제입니다.

거울을 설치할 수 있는 곳에 4가지 방법으로 설치 or 그냥 지나가기를 해줍니다.

 

dfs, bfs 둘 다 가능한 방법이지만 저는 bfs로 하였습니다.

bfs로 하면서 방문 체크를 해줘야합니다.

단순히 좌표로만 방문 체크를 해주면 방향처리가 안됩니다.

같은 지점이라도 방향에 따라 결과가 달라지기 때문에 나가는 방향에 따라서 방문 체크를 해줘야합니다.

 

또 최단거리 탐색과는 다르게 가중치가 거울의 사용횟수 입니다.

그러므로 우선순위 큐를 사용하여 사용한 거울의 갯수가 작은 순서대로 정렬시킵니다.

그러면 가장 먼저 다른 문에 도달했을 때가 정답이 됩니다.

 

<느낀 점>

 

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

struct point {
	int y, x, d, cnt;
};

int n, res = 2501;
char map[51][51];
bool visit[50][50][4];
int dy[4] = {0, -1, 0, 1 };
int dx[4] = {1, 0, -1, 0 };
int sy, sx;

struct cmp {
	bool operator()(point a, point b) {
		return a.cnt > b.cnt;
	}
};

priority_queue<point, vector<point>, cmp> q;

void bfs() {
	while (!q.empty()) {
		point t = q.top();
		q.pop();

		if (map[t.y][t.x] == '#' && !(t.y == sy && t.x == sx)) {
			cout << t.cnt << '\n';
			exit(0);
		}

		int ty = t.y + dy[t.d];
		int tx = t.x + dx[t.d];
		int td;
		int tcnt = t.cnt + 1;

		if (ty < 0 || ty >= n || tx < 0 || tx >= n ||
			map[ty][tx] == '*') continue;

		//그냥 가기
		if (!visit[ty][tx][t.d]) {
			q.push({ ty, tx, t.d, t.cnt });
			visit[ty][tx][t.d] = true;
		}

		if (map[ty][tx] == '!') {
			if (t.d == 0) {
				td = 1;
				if (!visit[ty][tx][td]) {
					q.push({ ty, tx, td, tcnt });
					visit[ty][tx][td] = true;
				}

				td = 3;
				if (!visit[ty][tx][td]) {
					q.push({ ty, tx, td, tcnt });
					visit[ty][tx][td] = true;
				}
			}
			if (t.d == 1) {
				td = 0;
				if (!visit[ty][tx][td]) {
					q.push({ ty, tx, td, tcnt });
					visit[ty][tx][td] = true;
				}

				td = 2;
				if (!visit[ty][tx][td]) {
					q.push({ ty, tx, td, tcnt });
					visit[ty][tx][td] = true;
				}
			}
			if (t.d == 2) {
				td = 1;
				if (!visit[ty][tx][td]) {
					q.push({ ty, tx, td, tcnt });
					visit[ty][tx][td] = true;
				}

				td = 3;
				if (!visit[ty][tx][td]) {
					q.push({ ty, tx, td, tcnt });
					visit[ty][tx][td] = true;
				}
			}
			if (t.d == 3) {
				td = 0;
				if (!visit[ty][tx][td]) {
					q.push({ ty, tx, td, tcnt });
					visit[ty][tx][td] = true;
				}

				td = 2;
				if (!visit[ty][tx][td]) {
					q.push({ ty, tx, td, tcnt });
					visit[ty][tx][td] = true;
				}
			}
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (map[i][j] == '#') {
				sy = i; sx = j;
			}
		}
	}

	for (int i = 0; i < 4; i++) {
		q.push({sy, sx, i, 0});
		visit[sy][sx][i] = true;
	}
	
	bfs();

	return 0;
}