[G4] 백준 2412번 암벽 등반 C++ 너비 우선 탐색, 해시맵

리뷰

 

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

해시맵을 기반으로 너비 우선 탐색을 수행하여 정상에 오르는 최소 시간을 구하는 문제

 

 

전역 변수

• Y : y좌표의 최대값을 정의할 상수 변수
• n : 홈의 개수를 저장할 변수
• t : 정상의 높이를 저장할 변수
• v : 홈의 좌표를 저장할 2차원 해시맵
• d : 이동할 수 있는 범위를 저장할 배열
• Pos : 현재 위치 좌표와 이동 횟수를 정의할 구조체

 

함수

1. bfs

int bfs() {
	queue<Pos> q;
	q.push({ 0, 0, 0 });

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y, cc = pos.c;
		//cout << cx << " " << cy << " " << cc << "\n";
		if (cy == t) return cc;

		for (int i = 0; i < 5; ++i) {
			int nx = cx + d[i];
			if (0 <= nx && nx <= Y) {
				for (int j = 0; j < 5; ++j) {
					int ny = cy + d[j];
					if (0 <= ny && ny <= Y && v[nx][ny]) {
						v[nx].erase(ny);
						q.push({nx, ny, cc + 1});
					}
				}
			}
			
		}
	}
	return -1;
}

 

너비 우선 탐색을 통해 산의 정상까지 걸리는 최소 이동을 구하기 위한 함수

 

문제풀이

1. n, t값을 입력 받고, n개의 홈의 위치 정보를 입력 받아 v배열에 해당 좌표를 true로 저장해 준다.
2. bfs함수를 호출한다. Pos타입의 큐 q를 초기화 하고 시작 좌표, 이동 횟수의 초깃값 0, 0, 0을 push해준다.
3. q가 빌때까지 while 루프를 수행하고, 매 루프마다 요소를 한개씩 뽑아내준다.
4. 현재 위치 좌표, 이동 횟수를 각각 변수 cx, cy, cc에 파싱해 준다.
5. 기저 조건으로 cy가 t에 도달한 경우 cc를 리턴해 준다.
6. 배열 d를 순회하며 x, y좌표를 탐색해 준다, 각 범위는 0과 Y를 포함한 범위 사이여야 한다.
7. 이동한 위치의 v값이 true라면 false로 변경 후 이동 위치와 이동 횟수를 1만큼 늘려 q에 푸시해준다.
8. while루프가 종료될 때까지 기저 조건에 도달하지 못한다면 -1을 리턴해 준다.
9. 리턴받은 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• x좌표는 최대 100만, y좌표는 최대 20만이므로 배열이 아닌 해시맵을 사용해 주었다.

 

정답 코드

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

const int Y = 2e5;
int n, t;
unordered_map<int, unordered_map<int, bool>> v;
int d[] = { -2, -1, 0, 1, 2 };
struct Pos {
	int x, y, c;
};

int bfs() {
	queue<Pos> q;
	q.push({ 0, 0, 0 });

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y, cc = pos.c;
		//cout << cx << " " << cy << " " << cc << "\n";
		if (cy == t) return cc;

		for (int i = 0; i < 5; ++i) {
			int nx = cx + d[i];
			if (0 <= nx && nx <= Y) {
				for (int j = 0; j < 5; ++j) {
					int ny = cy + d[j];
					if (0 <= ny && ny <= Y && v[nx][ny]) {
						v[nx].erase(ny);
						q.push({nx, ny, cc + 1});
					}
				}
			}
			
		}
	}
	return -1;
}

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

	cin >> n >> t;
	while (n--) {
		int x, y; cin >> x >> y;
		v[x][y] = true;
	}

	cout << bfs();
}