[G4] 백준 2253번 점프 C++ 너비 우선 탐색, 다이나믹 프로그래밍

리뷰

 

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

BFS + DP를 활용한 문제

 

 

전역 변수

• N : 배열 첫번째 인덱스의 최대값을 정의할 상수 변수
• J : 배열 두번쨰 인덱스의 최대값을 정의할 상수 변수
• n : 돌의 개수를 저장할 변수
• m : 밟을 수 없는 돌의 개수를 저장할 변수
• j : x칸을 점프해 n번째 돌을 밟았는지 여부를 체크하기 위한 배열
• cant : 밟을 수 없는 돌 정보를 저장할 배열
• Pos : 현재 위치와 진행 시간, 이전에 점프한 거리를 정의할 구조체
• dx : 점프 거리를 조절할 배열

 

함수

1. bfs

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

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

		for (int i = 0; i < 3; ++i) {
			int jump = pj + dx[i];
			if (jump <= 0) continue;
			
			int nx = cx + jump;
			if (1 <= nx && nx <= n && !cant[nx] && !j[nx][jump]) {
				j[nx][jump] = true;
				q.push({ nx, ct + 1, jump });
			}
		}
	}
	return -1;
}

 

1번 돌부터 N번 돌까지 도달이 가능하면 도달 시간을, 도달이 불가능하면 -1을 반환하는 함수

 

 

문제풀이

1. n, m값을 입력 받고, m개의 밟을 수 없는 돌의 좌표를 입력 받아 cant배열을 초기화한다.
2. bfs함수를 호출한다. Pos타입의 큐 q를 초기화 하고, 초기 좌표 1과 시간 0, 점프 거리 0을 추가한다.
3. q가 빌때까지 while루프를 순회하고, 매 루프마다 요소를 꺼내 변수 cx, ct, pj에 파싱한다.
4. 기저 조건으로 cx가 n에 도달했을 경우 ct를 반환한다.
5. dx배열을 순회하며 변수 jump에 점프할 거리를 초기화한다. 만약 jump가 0이하라면 continue처리한다.
6. 변수 nx에 cx+jump를 저장해 이동할 돌 번호를 저장한다.
7. nx가 1~n범위 내에 존재하고, 밟을 수 있는 돌이면서 아직 밟지 않은 돌이라면 이동을 진행한다.
8. 이동을 진행한 후엔 j[nx][jump]를 true로 저장하고, nx, ct+1, jump를 q에 삽입한다.
9. 만약 while루프가 종료될때까지 기저 조건에 도달하지 못한다면 -1을 반환한다.
10. bfs함수의 반환값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. N이 최대 1만이므로 계속 속도를 붙힌다면 최대 140칸을 점프할 수 있다. 따라서 J값을 140으로 정했다.
2. 좌표가 같더라도 점프한 거리가 다른 경우를 구분지어 주어야 한다.
3. 가중치가 별도로 존재하지 않으므로 큐와 방문 배열을 통해 최단 거리를 보장한다.

 

정답 코드

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

const int N = 1e4 + 1;
const int J = 140;
int n, m;
bool j[N][J];
bool cant[N];
struct Pos {
	int x, t, pj;
};
int dx[] = { -1, 0, 1 };

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

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

		for (int i = 0; i < 3; ++i) {
			int jump = pj + dx[i];
			if (jump <= 0) continue;
			
			int nx = cx + jump;
			if (1 <= nx && nx <= n && !cant[nx] && !j[nx][jump]) {
				j[nx][jump] = true;
				q.push({ nx, ct + 1, jump });
			}
		}
	}
	return -1;
}

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

	cin >> n >> m;
	while (m--) {
		int x; cin >> x;
		cant[x] = true;
	}

	cout << bfs();
}