백준 1697번: 숨바꼭질

문제

• https://www.acmicpc.net/problem/1697
• 전체 부분 집합들을 탐색하는 데 너비 우선 탐색 적용하기 (최단 경로 찾기)

기록 포인트

• 전체 부분 집합 탐색 과제를 너비 우선 탐색 방식으로 구성하는 과정
  • 백준 2295번 동전 문제와 접근 방식 동일 설명 링크
  • N에서 출발해 K에 도착하기 위한 최소거리를 f(N)라고 할 때,
    • f(N) = 1 + f(N-1) = 1 + f(N+1) = 1 + f(N*2)
  • 최소거리 계산을 K를 기준으로 역으로 계산한 값을 g(K)라고 할 때,
    • K가 짝수이면, g(K) = 1 + g(K-1) = 1 + g(K+1) = 1 + g(K//2)
    • K가 홀수이면, g(K) = 1 + g(K-1) = 1 + g(K+1)
    • 이 부분은 아래 '역으로 접근해 탐색 범위 줄이기' 참고
• 역으로 접근해 탐색 범위 줄이기
  • N에서 K로 가기 위한 다음 스텝을 찾으면, 다음 스텝은 N+1, N-1, N*2 (3개)
    • 이 때, N+1, N-1, N*2 모두 최소 거리의 중간 단계가 될 수 있으므로 탐색 범위에서 줄이지 못함
  • 반대로 K로 진입하기 위한 이전 스텝을 찾으면, K가 홀수 혹은 짝수인지에 따라 다름
    • K가 짝수이면 K/2 또한 정수이므로, 이전 스텝은 K-1, K+1, K/2 (3개)
    • K가 홀수이면 K/2 가 정수가 아니므로, 이전 스텝은 K-1, K+1 (2개)
      • 가령, K가 17이면 2배로 순간이동하여 K에 도착할 수 있는 N은 없으므로, 탐색 범위에서 줄일 수 있음
• 문제를 잘 파악해 탐색 범위를 제한하기
  • N에서 K로 올라가는 방식으로 구성 시 (1차 답안 참고)
    • 새로운 정점이 K의 최대값(10**6)을 초과하면 탐색 범위에서 제외해야 함
    • 이 부분을 놓쳐 계속 메모리 초과 발생
    • 아직 남은 의문은, 그렇다면 각 문제의 K를 기준으로도 탐색 범위를 제한할 수 있는 것 아닐지, 그러면 그 방법은 무엇일지 궁금함
  • K에서 N으로 내려오는 방식으로 구성 시 (최종 답안 참고)
    • 새로운 정점이 0보다 작아졌을 때 탐색 범위에서 제외해야 함

접근 방식

• 제출 답안 참고

제출 답안

최종 답안

• K에서 N으로 내려온 방식
  • v2가 0보다 작아지는 경우, 추가 탐색 대상에서 제외

import sys
from collections import deque
sys.stdin = open("./baekjoon/testcase.txt")

N, K = tuple(map(int, sys.stdin.readline().split()))

def BFS(s):
    parent = {s} # set   
    frontier = deque([(s, 0)])
    while frontier:
        v1, time1 = frontier.popleft()
        # 한 노드에서 이동할 수 있는 경우 3가지
        next_nodes = [v1+1,v1-1]
        if v1 % 2 == 0:
            next_nodes.append(v1//2)
        for v2 in next_nodes:
            time2 = time1+1
            # 이동 불가능한 지점인지 확인
            if v2 < 0:
                continue
            # 이미 방문한 위치인지 확인
            if v2 in parent:
                continue
            # 새로운 위치인 경우, 우선 목표 지점인지 확인
            if v2 == N:
                return time2
            # 새로운 위치이지만 목표 지점이 아닌 경우, 탐색 범위에 추가
            parent.add(v2)
            frontier.append((v2, time2))
    return False

s = K
if s == N:
    print(0)
else:
    time = BFS(s)
    print(time)

1차 답안

• N에서 K로 올라간 방식
  • v2가 K의 최대값을 초과하는 경우, 추가 탐색 범위에서 제외
    • 1차 답안에서는 이 부분을 놓쳐 메모리 초과 발생

import sys
from collections import deque

N, K = tuple(map(int, sys.stdin.readline().split()))

def BFS(s):
    parent = {s: None}    
    frontier = [s]
    time = 0
    while frontier:
        time += 1
        next_frontier = []
        for v1 in frontier:
            # 한 노드에서 이동할 수 있는 경우 3가지
            for v2 in [v1-1, v1+1, v1*2]:
                # 이미 방문한 위치인지 확인
                if v2 in parent:
                    continue
                # 새로운 위치인 경우, 우선 목표 지점인지 확인
                if v2 == K:
                    return time
                # 새로운 위치이지만 목표 지점이 아닌 경우
                # 새로운 탐색 대상인지 판단
                if v2 > 100000:
                    continue
                # 새로운 탐색 대상으로 판단될 경우
                parent[v2] = v1
                next_frontier.append(v2)
        # 새로운 깊이의 탐색 범위로 업데이트
        frontier = next_frontier
    return False

s = N
if s == K:
    print(0)
else:
    time = BFS(s)
    print(time)