[BOJ] 숨박꼭질 1697

출처:: https://www.acmicpc.net/problem/1697

 

1. 문제 이해 및 해결과정

-최소시간 구하는 문제 BFS

-현재 좌표가 0 ~ 100000 벗어나지 않고, 다음 좌표로 이동시 현재 좌표 + 1

2. 풀이방법

 1.[C++] BFS

#if 01
//숨박꼭질
// https://www.acmicpc.net/problem/1697

#include <iostream>
#include <queue>
#define MAX 100000
using namespace std;

int N, K;
int visited[MAX + 10];
queue<int> q;

int BFS() {
	q.push(N);
	visited[N] = 1;

	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		if (cur == K)return visited[cur]-1;

		if (cur - 1 >= 0 && visited[cur - 1] == 0) { //x-1
			q.push(cur-1);
			visited[cur-1] = visited[cur] + 1;
		}
		if (cur + 1 <= MAX && visited[cur + 1] == 0) { //x+1
			q.push(cur+1);
			visited[cur + 1] = visited[cur] + 1;
		}
		if (cur*2 <= MAX && visited[cur * 2] == 0) {//2*x
			q.push(cur*2);
			visited[cur *2] = visited[cur] + 1;
		}
		
		
	
	}

}
void InputData() {
	cin >> N >> K;
}
int main() {
	int sol;
	InputData();
	sol = BFS();
	cout << sol;
	return 0;
}

#endif

 

3부분 탐색하는 것을 아래 코드로 바꿀 수 있음

범위 기반 for 문 이라고 한다. 

void bfs() {
    queue<int> q;
    q.push(n);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        if (x == k) {
            printf("%d\n", dist[x]);
            return;
        }
        for (int nx : {x-1, x+1, 2*x}) {
            if (nx < 0 || nx > MAX) continue;
            if (dist[nx]) continue;
            q.push(nx);
            dist[nx] = dist[x]+1;
        }
    }
}


출처: https://rebas.kr/656 [PROJECT REBAS]

  2. [PYTHON] BFS

#숨바꼭질
#https://www.acmicpc.net/problem/1697
import sys
from collections import deque
sys.stdin = open("input.txt","r")
input=sys.stdin.readline

n,k=map(int,input().split())
MAX=100000
time=[0]*(MAX+1)
Q=deque()
Q.append(n)
while Q:
    cur=Q.popleft()
    if cur==k:
        print(time[cur])
        break
    for next in (cur-1,cur+1,cur*2):
        if 0<=next<=MAX and time[next]==0:
            time[next]=time[cur]+1
            Q.append(next)

 

3. 오답원인

 

4. 알게된 점

-범위기반 for문에 대해서 공부해봐야겠다.