(C++, Python3) - 백준(BOJ) 1697번 : 숨바꼭질

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

📕 풀이방법

📔 입력 및 초기화

1. 수빈이의 좌표 n, 동생의 좌표 k를 선언 후 입력받습니다.

 

2. 현재 탐색할 경로정보를 저장할 deque dq를 선언 후 현재 수빈의 좌표와 시간 0을 초기값으로 넣어줍니다.

 

3. 각 좌표 check배열을 선언 후 0에서 10만까지 위치에 존재할 수 있으므로 10만1의 크기를 선언해줍니다.

📔 풀이과정

함수 bfs를 구현해줍니다.1. dq에서 원소를 pop해 현재 좌표 pos가 k인지 비교해 맞다면 해당 time을 반환합니다.

 

2. 수빈이 현재 좌표에서 갈 수 있는 곳은 x-1, x+1, x*2이므로 범위를 초과하지 않으며 해당 좌표가 방문하지 않았다면 방문처리 후 dq에 append해줍니다.

 

* 도착하지 못하는 경우는 없지만 함수 반환형을 맞춰주기 위해 함수 끝에 -1을 반환해줍니다.

📔 정답 출력 | 반환

bfs함수 결과를 반환합니다.

---

📕 Code

📔 C++

#include <iostream>
#include <queue>
using namespace std;
int c[100001], N, K;
queue <int> q;
int BFS()
{
	q.push(N);
	c[N] = 1;
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		if (x == K) { return c[x] - 1; }
		if (x - 1 >= 0 && !c[x - 1]) { c[x - 1] = c[x] + 1; q.push(x - 1); }
		if (x + 1 <= 100000 && !c[x + 1]) { c[x + 1] = c[x] + 1; q.push(x + 1); }
		if (2 * x <= 100000 && !c[2 * x]) { c[2 * x] = c[x] + 1; q.push(2 * x); }
	}
}

int main() {
	cin >> N >> K;
	cout << BFS();
}

📔 Python3

import sys
from collections import deque
input = sys.stdin.readline
n,k = map(int, input().split())
dq = deque()
dq.append((n,0))
check = [0]*100001
check[n] = 1
def bfs():
    while dq:
        pos, time = dq.popleft()
        if pos == k:
            return time
        if pos-1 >= 0 and check[pos-1] == 0:
            check[pos-1] = 1
            dq.append((pos-1, time+1))
        if pos+1 <= 100000 and check[pos+1] == 0:
            check[pos+1] = 1
            dq.append((pos+1, time+1))
        if pos*2 <= 100000 and check[pos*2] == 0:
            check[pos*2] = 1
            dq.append((pos*2, time+1))
    return -1
print(bfs())

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.