[G5] 백준 1584번 게임 C++ 너비 우선 탐색, 우선순위 큐

리뷰

 

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

0, 0에서 500, 500까지 생명이 최소로 깎인 상태로 이동하는 문제

다익스트라로 구현할까 했지만 그냥 기저 조건에 도달하면 바로 리턴하는게 좋을 것 같아 bfs를 돌렸다.

 

 

전역 변수

1. n : 위험 구역의 개수를 저장할 변수
2. m : 죽음 구역의 개수를 저장할 변수
3. lst : 맵 정보를 저장할 정수형 2차 배열
4. v : 방문 정보를 저장할 논리형 2차 배열
5. dx, dy : 4방향 탐색을 하기 위한 방향 배열

 

함수

1. bfs

int bfs()

 

너비 우선 탐색을 사용해 시작 위치부터 목표 위치까지 생명을 가장 조금 사용하여 도착하는 경우를 구하는 함수

1. Pos타입의 우선순위 큐 q를 초기화 해주고, 초기값 0, 0, 0을 넣어준다.
2. v배열에 시작 좌표인 0, 0에 방문처리 후 q가 빌 때 까지 while루프를 수행해 준다.
3. 매 루프마다 요소를 한개씩 뽑아주며 위치와 소요 시간을 정수형 변수 cx, cy, ct로 파싱해 준다.
4. 기저 조건으로 만약 cx, cy가 둘다 500이라면 현재까지의 소요시간 ct를 리턴해 준다.
5. 4방향 탐색을 진행하며 맵의 범위 안에 있고, 맵 상에서 -1이 아니며 방문하지 않은 경우 이동을 진행해 준다.
6. 이동한 위치에 방문처리 후 맵 상에서 값이 1이면 시간을 늘려서, 아니면 시간을 그대로 q에 push해준다.
7. while루프가 종료될 때 까지 기저조건에 도달하지 못했다면 -1을 리턴해 준다.

 

문제풀이

1. n값을 입력 받고, n개의 위험 구역을 입력 받아 해당 구역의 넓이만큼 맵에 1로 저장해 준다.
2. m값을 입력 받고, m개의 위험 구역을 입력 받아 해당 구역의 넓이만큼 맵에 -1로 저장해 준다.
3. bfs함수를 호출하고 받은 리턴값을 출력해 준다.

 

트러블 슈팅

1. 로직을 완벽하게 짰는데 예제의 출력값이 정확하게 나오지 않았다.
2. x1 < x2, y1 < y2가 보장되지 않는 문제였다. 따라서 x1 > x2, y1 > y2일 경우 swap으로 두 값을 변경해 주었다.

 

참고 사항

• 가중치가 0 혹은 1인 경우만 있기에 다익스트라 보다 기저 조건에 도달하면 중간에 리턴하도록 로직을 짰다.
• 마찬가지로 0 혹은 1인 경우가 있기에 우선순위 큐를 통해 생명령을 가장 적게 잃은 경우를 우선 탐색 시켰다.

 

정답 코드

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

int n, m;
int lst[501][501];
bool v[501][501];
int dx[] = { 1, 0, 0, -1 };
int dy[] = { 0, 1, -1, 0 };

struct Pos {
	int x, y, t;
	bool operator<(const Pos& other) const {
		return t > other.t;
	}
};

int bfs() {
	priority_queue<Pos> q;
	q.push({ 0, 0, 0 });
	v[0][0] = true;

	while (!q.empty()) {
		Pos pos = q.top(); q.pop();
		int cx = pos.x, cy = pos.y, ct = pos.t;
		if (cx == 500 && cy == 500) return ct;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < 501 && 0 <= ny && ny < 501 && lst[nx][ny] != -1 && !v[nx][ny]) {
				v[nx][ny] = true;
				if (lst[nx][ny]) q.push({ nx, ny, ct + 1 });
				else q.push({ nx, ny, ct });
			}
		}
	}
	return -1;
}

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

	cin >> n;
	while (n--) {
		int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
		if (x1 > x2) swap(x1, x2);
		if (y1 > y2) swap(y1, y2);
		for (int i = x1; i <= x2; ++i)
			for (int j = y1; j <= y2; ++j)
				lst[i][j] = 1;
	}

	cin >> m;
	while (m--) {
		int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
		if (x1 > x2) swap(x1, x2);
		if (y1 > y2) swap(y1, y2);
		for (int i = x1; i <= x2; ++i)
			for (int j = y1; j <= y2; ++j)
				lst[i][j] = -1;
	}
	cout << bfs();
}