[G5] 백준 28069번 김밥천국의 계단 C++ 너비 우선 탐색

리뷰

 

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

주어진 연산을 통해 N번째 계단까지 K번 이내로 도달할 수 있는지 여부를 확인하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 목표 계단의 위치를 저장할 변수
• k : 계단을 오르는 최대 횟수를 저장할 변수
• v : 방문한 최단 시간을 저장할 배열
• Pos : 현재 위치와 누적 시간을 정의할 구조체

 

함수

1. up

void up(int x, int t, queue<Pos>& q) {
	if (x > n || v[x] <= t || t > k) return;
	v[x] = t;
	q.push({ x, t });
}

 

계단을 오를 수 있는지 여부를 체크하고, 오르는 기능을 구현한 함수

 

2. bfs

string bfs() {
	queue<Pos> q;
	q.push({ 0, 0 });
	v[0] = 0;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int x = pos.x, t = pos.t;

		if (x == n) return "minigimbob";

		up(x + 1, t + 1, q);
		up(x + x / 2, t + 1, q);
	}
	return "water";
}

 

너비 우선 탐색을 통해 n번째 계단에 도달 가능한지 여부를 확인하기 위한 함수

 

 

문제풀이

1. n, k값을 입력 받고, n개의 계단의 초기값을 매우 큰 수로 저장하여 v배열을 초기화한다.
2. bfs함수를 호출한다.
3. Pos타입의 큐 q를 초기화 하고, 초기값 {0, 0}을 push한다, 초기 위치의 도달 시간을 0으로 초기화한다.
4. q가 빌때까지 while루프를 순회하고, 매 루프마다 요소를 꺼내 변수 x, t에 파싱한다.
5. 기저 조건으로 x가 n일 경우 "minigimbob"을 리턴한다.
6. up함수에 x+1, t+1, q를 매개변수로 전달하여 오를 수 있다면 q에 추가한다.
7. up함수에 x+x/2, t+1, q를 매개변수로 전달하여 오를 수 있다면 q에 추가한다.
8. 만약 기저 조건에 도달하지 못한 채로 while루프가 종료되면 "water"를 리턴한다.
9. bfs함수의 리턴값을 출력한다.

 

트러블 슈팅

1. up함수에서 x가 n보다 커진 경우를 체크해주지 않아 OOB에러가 발생했다.
2. x가 n보다 클 경우 조기 종료 처리해주어 AC를 받았다.

 

참고 사항

1. 방문 처리를 boolean형태로 한다면 더 좋은 조건이 발생했을 때의 연산이 불가능할수도 있다고 생각했다.

 

정답 코드

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

const int N = 1e6 + 1;
int n, k;
int v[N];
struct Pos {
	int x, t;
};

void up(int x, int t, queue<Pos>& q) {
	if (x > n || v[x] <= t || t > k) return;
	v[x] = t;
	q.push({ x, t });
}

string bfs() {
	queue<Pos> q;
	q.push({ 0, 0 });
	v[0] = 0;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int x = pos.x, t = pos.t;

		if (x == n) return "minigimbob";

		up(x + 1, t + 1, q);
		up(x + x / 2, t + 1, q);
	}
	return "water";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	for (int i = 0; i <= n; ++i) v[i] = 2e9;
	cout << bfs();
}