Notice
Recent Posts
Recent Comments
Link
Seung's Learning Record
백준#1697 숨바꼭질 본문
난이도 : 실버1
소요시간 : 1시간 28분
사용한 풀이법 : dfs,queue
풀이 과정
1. 수빈 현 위치로 부터의 거리 측정용 배열 dist[], 이동 가능 위치 체크용 큐 Q[] 생성;
2. dist[]는 -1로 초기화, Q[]에 수빈 현위치 push;
3. dist[k]에 값이 들어가기 전까지 while 루프{}
4. 현위치 확인용 변수 cur에 Q.front() 대입;
5. cur이 -1, +1,*2 일때의 상황 for문 돌리면서 bfs 진행
6. 조건 충족 시, 해당 상황의 dist 값을 dist[cur]+1로 설정;
7. while 탈출 시 dist[k]값 출력;
#include <iostream>
#include <queue>
using namespace std;
queue<int> Q;
int dist[100002];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,k;
cin >> n >> k;
fill(dist,dist+100001,-1);
dist[n]=0;
Q.push(n);
while(dist[k]==-1){
int cur = Q.front();
Q.pop();
for(int i=0; i<3; i++){
int pos = (i == 0)?cur-1 : (i ==1)?cur+1 : cur*2;
if(pos<0 || pos>100000) continue;
if(dist[pos]!=-1) continue;
dist[pos] = dist[cur]+1;
Q.push(pos);
}
}
cout << dist[k] << '\n';
}
'알고리즘' 카테고리의 다른 글
백준 #10026 적록색약 (1) | 2024.02.11 |
---|---|
백준 #1012 유기농 배추 (0) | 2024.02.11 |
재귀 / 백트래킹 (0) | 2023.11.13 |
깊이 우선 탐색 / DFS (0) | 2023.11.11 |
너비 우선 탐색 / BFS (1) | 2023.11.09 |