BOJ_1697 숨바꼭질

• TOC {:toc}

이 글은 백준 온라인 저지의 1697번 문제를 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.06.27 (Python)

import sys
sys.setrecursionlimit(10 ** 8)

N, K = map(int, input().split())

LIMIT = 100000
visited = [False] * (LIMIT + 1)
visited[N] = True

def bfs(queue, count):
    global visited

    tmp = []
    while queue:
        n = queue.pop()
        if n == K:
            return count
        for x in [n - 1, n + 1, 2 * n]:
            if 0 <= x <= LIMIT and not visited[x]:
                visited[x] = True
                tmp = [x] + tmp
    count += 1

    return bfs(tmp, count)

print(bfs([N], 0))

# popleft와 append를 이용해서 푸는 코드
import sys
from collections import deque
sys.setrecursionlimit(10 ** 8)

N, K = map(int, input().split())

LIMIT = 100000
visited = [False] * (LIMIT + 1)
visited[N] = True

def bfs(queue, count):
    global visited
    queue = deque(queue)

    tmp = []
    while queue:
        # 순서가 상관없어도 pop을 써도 괜찮을 거 같긴 하다.
        n = queue.popleft()
        if n == K:
            return count
        for x in [n - 1, n + 1, 2 * n]:
            if 0 <= x <= LIMIT and not visited[x]:
                visited[x] = True
                tmp.append(x)
    count += 1

    return bfs(tmp, count)

print(bfs([N], 0))

아이디어 & 풀이

목적지의 깊이가 얕을수록 이동 경로와 시간이 짧을 테니 너비 우선 탐색을 사용한다.

• 현재 노드 n에 인접한 노드를 [n - 1, n + 1, 2 * n]으로 구성해 이전에 방문하지 않았다면 큐에 추가한다.
  • 이동할 수 있는 노드는 0 ~ 100,000 사이이므로 큐에 추가하기 전에 각 값이 이 범위 안에 있는지 확인해야 한다.
• 너비 우선 탐색의 자세한 진행 과정은 [boj-1260]{1260번} 문제를 참고한다.

일반 너비 우선 탐색과 다른 점은 현재 깊이를 파악해야 한다는 점이다.

• 이는 현재 깊이로 이동하는데 걸린 경로의 단계이자 걸린 시간과 같기 때문이다.
• 깊이 값을 count 변수로 관리해주고 현재 노드가 목적지와 같으면 그 값을 반환하면 된다.

이를 반영하면 진행이 다음과 같이 바뀐다.

• 현재 queue 안의 원소를 pop 하면서 이동할 수 있는 노드를 바로 queue에 추가하는 것이 아니라 tmp로 큐를 따로 구성해 추가한다.
• 현재 깊이의 노드, 즉 queue안의 원소를 모두 pop 하면 count를 1 추가한다.
• 새로 구성한 queue와 현재 깊이인 count를 새로운 인자로 동일 과정을 다시 수행한다.

디버그

• n가 범위 내의 수라도 x(e.g., n + 1, 2 * n)는 범위 외의 수 일 수 있기 때문에, visited[x]에서 out of range 에러가 발생한다.
  • not visited[x] 조건 앞에 x의 범위를 확인하는 조건을 추가한다.
• recursion 에러도 발생해서 recursionlimit 값도 수정했다.

피드백

• 시간이 오래 걸리고 용량도 엄청나게 먹었다.
  • popleft가 아닌 pop을 사용하기 위해 작성한 tmp = [x] + tmp 과정이 시간을 엄청 많이 쓴 것 같다.
• 비슷한 주제의 이전 문제의 풀이에 얽매이면 안될 것 같다.
  • 이전의 풀이를 그대로 사용하려고 하니까 비효율적으로 작성하게 된다.
  • 실제로 이번 풀이는 pop을 유지하고 tmp = [x] + tmp를 사용하는 것보다 popleft()와 append를 쓰는 게 훨씬 빨랐다.
  • 어떤 조건이 있기 때문에 그런 풀이를 써야 하는지 확실히 하고 필요할 때만 쓰는 연습을 해야겠다.

2022.04.05 (JS)

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim();

function bfs() {
    const visited = Array(LIMIT + 1).fill(false);
    let queue = [N];
    visited[N] = true;
    count = 0;

    while (queue.length) {
        const tmp = [];
        for (const n of queue) {
            if (n === K) return count;
            for (const next of [n + 1, n - 1, n * 2]) {
                if (!visited[next] && 0 <= next && next <= LIMIT) {
                    visited[next] = true;
                    tmp.push(next);
                }
            }
        }
        queue = tmp;
        count += 1;
    }
}

const [N, K] = input.split(" ").map((n) => parseInt(n));
const LIMIT = 100000;
console.log(bfs());

디버그

• visited 원소 개수를 처음에 100000개로 해서 시작하자 마자 틀렸다. 100001개로 수정
• K와 비교하는 조건을 다음 이동 지점을 추가하는 코드 안에 넣으니까 N과 K가 바로 일치하는 조건에서 출력을 제대로 못했다. count가 0일 수도 있어서 queue에서 n을 꺼내자마자 비교해야 한다.
• 2배 증가해서 K 값을 넘는 값으로 이동한 다음에 뒤로 가는 게 더 빠를 수도 있어서 작거나 같은 값이 K가 아니고 100000이어야 한다.

참고 답안 1

# 풀이 1-1
N, K = map(int, input().split())

LIMIT = 100000
visited = [False] * (LIMIT + 1)
visited[N] = True
count = 0

def bfs(queue):
    global visited
    global count

    while queue:
        tmp = []
        for n in queue:
            if n == K:
                return count
            for x in [n - 1, n + 1, 2 * n]:
                if 0 <= x <= LIMIT and not visited[x]:
                    visited[x] = True
                    tmp.append(x)
        queue = tmp
        count += 1

print(bfs([N]))

# 풀이 1-2
N, K = map(int, input().split())

LIMIT = 100000
visited = [False] * (LIMIT + 1)
visited[N] = True
queue = [N]
count = 0

while not K in queue:
    tmp = []
    for n in queue:
        for x in [n - 1, n + 1, 2 * n]:
            if 0 <= x <= LIMIT and not visited[x]:
                visited[x] = True
                tmp.append(x)
    queue = tmp
    count += 1

print(count)

아이디어 & 풀이

진행은 위의 풀이와 동일하지만, 재귀를 사용하지 않아도 된다.

• count는 굳이 인자로 넘기지 않아도 별도의 전역변수로 관리하면 된다.
• queue ‘전체 원소’를 다 pop 한 다음 tmp를 새로운 큐로 사용하기 때문에
  • 재귀를 사용하지 않고 queue를 순회하되, queue에 원소가 없을 때 queue를 tmp로 바꿔주면 된다.
  • 큐의 pop과 push가 섞이지 않고 인접한 노드를 순회하는 순서가 중요하지 않기 때문에 pop과 push 하는 위치(리스트 처음, 뒤)를 신경 쓰지 않아도 된다.
  • 즉, 시간이 오래 걸리는 popleft나 appendleft를 사용하지 않고 이미 만들어진 queue의 원소를 순회하면 된다.
• 풀이 1-2 에서는 종결 조건을 while문 안에 넣어서 확인했다.

참고 답안 2

def sec(n, k):
    if n >= k:
        return n - k
    elif k == 1:
        return 1
    elif k % 2:
        return 1 + min(sec(n, k - 1), sec(n, k + 1))
    else:
        return min(k - n, 1 + sec(n, k // 2))

N, K = map(int, input().split())
print(sec(N, K))

아이디어 & 풀이

N이 K로 갈 때 큰 수(앞)로 가는 방법은 N + 1, 2 * N 두 가지, 작은 수(뒤)로 가는 방법은 N - 1로 한 개이다.

우선, N이 K보다 큰 경우는 N이 전체적으로 뒤로 가야 한다.

• N이 K로 최단 거리로 가기 위해서는 앞으로 가지 않고 뒤쪽으로 1칸씩 이동해야 한다.
• 결과적으로 이동하는 데 걸리는 시간은 N에서 K와의 거리, N - K 이다.

N보다 K가 큰 경우는 앞과 뒤를 방향을 섞어서 다음과 같이 이동한다.

• 앞으로 갈 때는 N + 1보다 2 * N으로 이동하는 것이 더 빠르다.
• 2 * N으로 이동하다 보면 K를 지나칠 수 있기 때문에 적절한 때마다 N - 1로 뒤로 한 칸 이동해야 한다.
• N에서 K로 이동하면 각 이동의 적절한 타이밍을 잡기가 쉽지 않다.

도착점(K)부터 생각하면 2를 곱해서 이동한 부분을 확실히 알 수 있기 때문에 진행을 역으로 하면 각 이동을 선택하기 훨씬 쉽다.

• 현재 수(K)가 2로 나뉘지 않는 경우
  • 현재 위치는 K - 1에서 이동했거나 K + 1에서 이동한 것이다.
  • 둘 중(sec(N, K -1), sec(N, K + 1)) 더 작은 값을 선택한 뒤 그 시간에 1초를 더하면 현재 위치 K까지 오는 데 걸린 시간이 된다.
• 현재 수(K)가 2로 나뉘는 경우
  • 현재 위치는 K // 2에서 이동했을 때 한 번에 가장 많은 거리를 이동한 것이기 때문에 일반적으로 가장 빠르다고 볼 수 있다.
    • 이 경우 현재 위치 K까지 오는데 걸린 시간은 sec(N, K // 2)에서 1초 더한 시간과 같다.
  • K // 2가 N보다 작아지면 걸리는 시간이 N - (K // 2)가 된다.
    • N - (K // 2) + 1이 K - N보다 클 수 있고, 이 경우 sec(N, K // 2) + 1이 걸린 시간의 최솟값이 아니게 된다.
  • 이를 고려해 최종적으로 dis(N, K // 2)에 1초를 더한 값과 K - N중 둘 중 더 작은 값을 고르면 된다.

점의 범위가 0 ~ 100,000 이기 때문에 N과 K의 범위가 여기서 벗어나는 것을 방지해야한다.

• N과 K가 이동할 수 있는 최소점은 각각 0과 1이다.
• K가 1일 때를 종결 조건으로 0에서 1까지의 이동시간인 1을 반환한다.

K가 2로 나눠질 때 K - 1이나 K + 1에서 1초 더한 것을 고려하지 않는 정확한 이유 고민해보기

• 우선 현재 상황에서 N과 K의 관계는 다음과 같다: K // 2 < N < K, sec(N, K)= K - N > N - (K // 2) + 1