1697번 - 숨바꼭질

💡 1차원 bfs 유형 (코테 스터디에서 나온 접근을 살펴보자)

import sys
from collections import deque

input = sys.stdin.readline

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

if N == K:
    print(0)
    exit(0)

visited = [False] * 100001

def bfs():
    
    cnt = 0
    
    dq = deque()
    dq.append((N,cnt))
    visited[N] = True
    
    while dq:
        x, cnt = dq.popleft()
        for nx in [x-1, x+1, x*2]:

            if 0 <= nx <= 100000 and visited[nx] is False:
                if nx == K:
                    print(cnt+1)
                    return
                else:
                    visited[nx] = True
                    dq.append((nx, cnt+1))

bfs()

• 이번 문제는 코테 스터디에서 들었던 기발한 풀이법이 계속 머리속에 남는다..ㅋㅋㅋ
• 일단 이번 문제는 그렇게 어렵지 않게 접근했던거 같다.
• 동생의 위치는 K로 고정되어 있고, 수빈이 N에서 계속 적으로 움직이는 것이기 떄문에,시작점을 N으로 잡고 이동가능 경우의 수를 [n-1,n+1,2*n] 총 3개의 경우로 bfs를 적용하였다.
• visited 배열을 선언하여 지금까지 방문한 위치에는 중복으로 가지않도록 설정하여, 가장 빠른 시간을 출력하려고 하였다.

💡 코테 스터디에서 나온 기발한 풀이법

서현님

from sys import stdin as s
from collections import deque

N, K = map(int, s.readline().split())

X = max(N, K) + 2
dp = [-1] * X
dp[N] = 0
dq = deque()
dq.append(N)

while dq:
    x = dq.popleft()
    if x == K:
        print(dp[x])
        exit()
    for y in [x+1, x-1, x*2]:
        if 0<=y<X and dp[y]==-1:
            dp[y] = dp[x]+1
            dq.append(y)

• 위 코드와 같이 수빈이 이동할 수 있는 최대 경로를 X = max(N,K) + 2로 설정하였다.

  ex) 1, 15
  16 - 1 을 고려하기 위해서 + 2를 진행해줘야 한다.
  이렇게 하면 *2가 될수 있는 최댓값까지 고려가 가능하다.
  굳이 배열을 최댓값까지 고려해줄 필요가 없다

  x / x+1 / x+2 / x+3
  =>x+3은 x+1로 대처가 가능하다.

• 설명을 추가하자면, 수빈이 갈수있는 최대값은 동생의 위치 +2까지만 구하면 된다.
  왜냐하면 2를 고려해야 하기때문에 +1을 하게되면 2를 고려하지 못하게 되고, +3을 하게되면 사실 이는 최소값을 구하는 시점에서 +1로 대체가 가능하기 떄문에 최종적으로 +2까지만 고려하면 된다.