[G3] 백준 2151번 거울 설치 C++ 다익스트라

리뷰

 

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

최소한의 거울을 설치하여 한쪽 문에서 다른 문으로 이동하는 경로를 찾는 문제

 

 

전역 변수

• n : 맵의 가로/세로 길이를 저장할 변수
• sx, sy : 탐색을 시작할 문의 좌표를 저장할 변수
• ex, ey : 도착할 문의 좌표를 저장할 변수
• lst : 맵 정보를 저장할 문자열 배열
• bool : 설치한 거울의 개수로 방문 정보를 체크할 배열
• Pos : 시뮬레이션 시 사용할 현재 좌표 x, y, 현재 방향 d, 설치한 거울의 수 c를 정의할 구조체, c를 기준으로 오름차순 정렬해 준다.
• dx, dy : 4방향 탐색을 위한 방향 배열

 

함수

1. dijkstra

int dijkstra()

 

다익스트라를 사용해 출발 문에서 도착 문까지 이동할 때 최소 설치 거울의 개수를 구하는 함수

1. Pos 타입의 우선순위 큐 pq를 초기화 한다.
2. 초기 좌표에서 4방향 정보를 담고, 거울 설치 개수 0으로 총 4개를 push해준다.
3. 거울 설치 횟수가 0이면서 시작 좌표인 지점에 방문 처리를 진행해 준다.
4. pq가 빌 때 까지 while 루프를 수행하고, 매 루프마다 요소를 한 개씩 꺼내어 준다.
5. 기저 조건으로 만약 문에 도착한 경우 현재 거울 설치 개수를 리턴해 준다.
6. 현재 방향으로 쭉 탐색하며 맵의 범위 안에 있으며 벽을 만나지 않았고 방문 하지 않았다면 이동을 진행한다.
7. 이동한 위치가 거울 설치 가능한 지역이라면 설치 개수를 늘려 해당 위치를 방문 처리해 준다.
8. 이동한 좌표와 진행 방향에서 좌우 방향, 설치 개수를 늘린 구조체를 pq에 push해준다.
9. 만약 문을 만난 경우 방문 처리 후 pq에 삽입해 준 후 continue 처리해 준다.

 

문제풀이

1. n값을 입력 받고, 변수 idx를 0으로 초기화 해준다.
2. n * n크기의 맵 정보를 입력 받고, 문이 입력으로 들어온 경우 좌표를 저장해 준다.
3. 만약 idx가 0이라면 sx, sy에 시작 문의 위치를 저장하고 idx를 1만큼 증가시켜 준다.
4. idx가 0이 아니라면 ex, ey에 도착 문의 위치를 저장해 준다.
5. dijkstra 함수를 호출하고 리턴 받은 값을 출력해 준다.

 

트러블 슈팅

1. 초기엔 백트래킹 + BFS로 탐색을 진행하였으나, 거울의 개수를 문제에서 알려주지 않아 시간 초과를 받았다.
2. 이후 다익스트라 로직을 구현하고 제출을 하였으나 v배열에서 거울의 개수를 50개로 잡았더니 Fail을 받았다.
3. v배열의 크기를 거울이 나올 수 있는 최대값으로 설정하여 제출하였더니 AC를 받았다.

 

참고 사항

• v배열을 2500 * 50 * 50으로 설정하니 제출을 받은걸 보아 거울의 개수가 매우 많은 경우도 존재하는 것 같다.
• 논리형 배열로 초기화 한다면 메모리 면에서도 크게 영향을 받지 않는 것 같다.

 

정답 코드

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

int n, sx, sy, ex, ey;
string lst[50];
bool v[2500][50][50];
struct Pos {
	int x, y, d, c;
	bool operator<(const Pos& other) const {
		return c > other.c;
	}
};
int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };

void print(int x, int y) {
	cout << "\n";
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (i == x && j == y) cout << "@";
			else cout << lst[i][j];
		}
		cout << "\n";
	}
}

int dijkstra() {
	priority_queue<Pos> pq;
	for (int i = 0; i < 4; ++i) pq.push({ sx, sy, i, 0 });
	v[0][sx][sy] = true;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, cy = pos.y, cd = pos.d, cc = pos.c;
		if (cx == ex && cy == ey) return cc;

		int nx = cx + dx[cd], ny = cy + dy[cd];
		while (0 <= nx && nx < n && 0 <= ny && ny < n && lst[nx][ny] != '*' && !v[cc][nx][ny]) {
			if (lst[nx][ny] == '!') {
				v[cc + 1][nx][ny] = true;
				pq.push({ nx, ny, (cd + 1) % 4, cc + 1 });
				pq.push({ nx, ny, (cd + 3) % 4, cc + 1 });
			}
			else if (lst[nx][ny] == '#') {
				v[cc][nx][ny] = true;
				pq.push({ nx, ny, -1, cc });
				continue;
			}
			nx += dx[cd];
			ny += dy[cd];
		}
	}
	return -1;
}

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

	cin >> n;
	int idx = 0;
	for (int i = 0; i < n; ++i) {
		cin >> lst[i];
		for (int j = 0; j < n; ++j) {
			if (lst[i][j] == '#') {
				if (!idx) {
					sx = i, sy = j;
					idx++;
				}
				else ex = i, ey = j;
			}
		}
	}
	cout << dijkstra();
}