[Python][C++] 1697번 숨바꼭질

문제

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

 

 

코드

1. Python

from collections import deque

def bfs():
    q = deque()
    q.append(n)  # 시작점 n을 큐에 추가
    while q:  # 큐가 비어있지 않을 동안 반복
        x = q.popleft()  # 큐의 첫 번째 요소를 꺼냄
        if x == k:  # 현재 위치가 동생의 위치(k)와 같다면
            print(dist[x])  # 이동 횟수를 출력
            break  # 탐색을 종료
        for nx in (x - 1, x + 1, x * 2):  # 이동 가능한 위치들에 대해 반복
            if 0 <= nx <= MAX and not dist[nx]:  # 이동 가능한 위치가 유효 범위 내에 있고 아직 방문하지 않았다면
                dist[nx] = dist[x] + 1  # 현재 위치까지의 이동 횟수에 1을 더해 저장
                q.append(nx)  # 다음 위치를 큐에 추가

MAX = 10 ** 5
dist = [0] * (MAX + 1)  # 각 위치까지의 이동 횟수를 저장할 리스트를 초기화

n, k = map(int, input().split())

bfs()  # BFS 함수 호출

 

2. C++

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

const int MAX = 100001; // 최대 위치값을 설정

void bfs(int n, int k) {
    vector<int> visited(MAX, -1); // 각 위치의 방문 여부와 거리를 저장할 벡터를 -1로 초기화
    queue<int> q; // BFS를 위한 큐

    q.push(n); // 시작 위치를 큐에 추가
    visited[n] = 0; // 시작 위치의 방문 여부를 0으로 설정 (시작점이므로 이동 횟수는 0)

    while (!q.empty()) { // 큐가 비어있지 않을 동안 반복
        int v = q.front(); // 큐의 첫 번째 요소를 꺼냄
        q.pop(); // 큐에서 꺼낸 요소를 제거

        if (v == k) { // 현재 위치가 목표 위치와 같다면
            cout << visited[v]; // 이동 횟수를 출력
            return; // 탐색을 종료
        }

        // 현재 위치에서 이동할 수 있는 세 가지 경우에 대해 반복
        for (int nv : {v - 1, v + 1, v * 2}) {
            // 이동 가능한 위치가 유효 범위 내에 있고 아직 방문하지 않았다면
            if (nv >= 0 && nv < MAX && visited[nv] == -1) {
                q.push(nv); // 다음 위치를 큐에 추가
                visited[nv] = visited[v] + 1; // 현재 위치까지의 이동 횟수에 1을 더해 저장
            }
        }
    }
}

int main() {
    int n, k;

    cin >> n >> k; // 사용자로부터 시작 위치(n)와 목표 위치(k)를 입력받음

    bfs(n, k); // BFS 함수 호출

    return 0;
}

 

 

풀이 

백준 1463번과 같은 방식으로 접근하면 된다.

 

풀이 참고

https://ehdbs0903.tistory.com/entry/PythonC-1463번-1로-만들기

[Python][C++] 1463번 1로 만들기