[BOJ] 1697 숨바꼭질(BFS)
1. 문제
https://www.acmicpc.net/problem/1697
2. 아이디어
최단거리를 찾는 문제이므로 BFS를 이용하여 해결하였다.
BFS문제를 풀 때,
- 다음 방문할 위치가 범위를 벗어나지 않는지
- 다음 방문할 위치를 아직 방문하지 않았는지
확인하고 두 조건에 모두 부합한다면 다음 위치를 큐에 넣고 방문처리를 한다.
3. 풀이과정
1) ⭕RIGHT⭕
- 코드
#include <iostream>
#include <queue>
using namespace std;
int visited[100001];
int dist[100001]; // 얼마만큼 걸려서 갔는지 표시
void BFS(int pos) {
queue<int> q;
q.push(pos);
visited[pos] = 1;
while (!q.empty()) {
int current_pos = q.front();
q.pop();
if ((current_pos - 1 >= 0) && (visited[current_pos - 1] == false)) {
q.push(current_pos - 1);
visited[current_pos - 1] = true;
dist[current_pos - 1] = dist[current_pos] + 1;
}
if ((current_pos + 1 <= 100000) && (visited[current_pos + 1] == false)) {
q.push(current_pos + 1);
visited[current_pos + 1] = true;
dist[current_pos + 1] = dist[current_pos] + 1;
}
if ((current_pos * 2 <= 100000) && (visited[current_pos * 2] == false)) {
q.push(current_pos * 2);
visited[current_pos * 2] = true;
dist[current_pos * 2] = dist[current_pos] + 1;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int N, K;
cin >> N >> K;
visited[N] = 1;
dist[N] = 0;
BFS(N);
cout << dist[K];
return 0;
}
Author And Source
이 문제에 관하여([BOJ] 1697 숨바꼭질(BFS)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@pyh-dotcom/BOJ-1697-숨바꼭질저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)