[Baekjoon]백준 1697 숨바꼭질(실버 1) - Python/C/C++

문제설명

문제를 살펴보면 이때까지의 문제 유형과는 사뭇 다르다

2차원 배열에서 경로를 찾아나간것과는 다르게 1차원 배열에서 경우의 수를 찾는 문제이다

문제의 목표가 수빈이의 위치에서 동생의 위치까지 가는 가장 빠른 시간을 구하는 것이기 때문에 bfs가 가장 효율적이다

bfs는 시작점으로부터 거리가 1인 모든 정점, 거리가 2인 모든 정점...과 같은 방식으로 동작하므로

목표 지점에 도달하였을 때 그 경로가 최단 경로임을 보장할 수 있다

 

이전에는 dx = [-1, 1, 0, 0]과 같은 방식으로 방향을 설정하였지만 해당 문제에서는 순간이동(곱하기)도 존재하기 때문에

어떻게 해결할지 고민하다가 python에서 for문의 range 부분을 활용하였다

for nx in (x-1, x+1, x*2)를 통해 각각의 경우에 대해 확인을 하며 값을 최신화해나간다

distance 배열에는 최단 시간을 기록함과 동시에 방문을 확인하는 두 가지 역할을 수행하게 된다

import sys
from collections import deque
input = sys.stdin.readline

def bfs(x):
    queue = deque([x])
    while queue:
        x = queue.popleft()
        if x == sibling:
            return distance[x]
        for nx in (x-1, x+1, x*2):
            if 0 <= nx <= MAX and not distance[nx]:
                distance[nx] = distance[x] + 1
                queue.append(nx)
                
MAX = 100000
distance = [0] * (MAX + 1)
subin, sibling = map(int, input().split())
print(bfs(subin))

여기서 주의할 점은 distance 리스트를 생성할때, 문제에서 0 이상 100,000이하라고 했으므로

distance의 배열은 100001의 크기여야한다

(이상을 못보고 100000으로 만들었다가 IndexError가 발생하였다)

#include <stdio.h>

#define MAX 100000

int queue[MAX+1];
int dis[MAX+1];
int front = 0;
int rear = 0;

int bfs(int x, int y) {
    queue[rear++] = x;
    while(front < rear) {
        int idx = queue[front++];
        if(idx == y)
            return dis[idx];

        // python에서 x-1에 해당하는 코드
        int nx1 = idx-1;
        if(nx1 >= 0 && nx1 <= MAX && dis[nx1] == 0) {
            dis[nx1] = dis[idx] + 1;
            queue[rear++] = nx1;
        }

        // python에서 x+1에 해당하는 코드
        int nx2 = idx+1;
        if(nx2 >= 0 && nx2 <= MAX && dis[nx2] == 0) {
            dis[nx2] = dis[idx] + 1;
            queue[rear++] = nx2;
        }

        // python에서 x*2에 해당하는 코드
        int nx3 = idx*2;
        if(nx3 >= 0 && nx1 <= MAX && dis[nx3] == 0) {
            dis[nx3] = dis[idx] + 1;
            queue[rear++] = nx3;
        }
    }
}

int main() {
    int subin, sibling;
    scanf("%d %d", &subin, &sibling);
    printf("%d\n", bfs(subin, sibling));

    return 0;
}

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

const int MAX = 100000;
int dis[MAX + 1];

int bfs(int x, int y) {
    queue<int> q;
    q.push(x);

    while (!q.empty()) {
        int idx = q.front();
        q.pop();
        if (idx == y)
            return dis[idx];

        // python에서 x-1에 해당하는 코드
        int nx1 = idx - 1;
        if (nx1 >= 0 && nx1 <= MAX && dis[nx1] == 0) {
            dis[nx1] = dis[idx] + 1;
            q.push(nx1);
        }

        // python에서 x+1에 해당하는 코드
        int nx2 = idx + 1;
        if (nx2 >= 0 && nx2 <= MAX && dis[nx2] == 0) {
            dis[nx2] = dis[idx] + 1;
            q.push(nx2);
        }

        // python에서 x*2에 해당하는 코드
        int nx3 = idx * 2;
        if (nx3 >= 0 && nx3 <= MAX && dis[nx3] == 0) {
            dis[nx3] = dis[idx] + 1;
            q.push(nx3);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int subin, sibling;
    cin >> subin >> sibling;

    cout << bfs(subin, sibling) << endl;

    return 0;
}