백준 1697번 숨바꼭질 파이썬

리뷰

bfs로 해결하였다. if문에서 순서를 잘못 배치해서 계속 indexError가 났다.. 휴

 

문제 풀이   

1. 현재 위치 n과 목표 위치 k를 변수로 받아오고 방문 처리할 리스트를 100001 크기로 생성한다. 0 에서 10만 범위
2. 방향은 현재 위치 x에서 -1 혹은 1로 이동하거나 *2인 위치로 이동하는 것이니 -1 및 1만 생성해 준다.
3. 현재 위치, 이동 수를 튜플로 bfs를 실행한다. 입력받은 튜플을 큐에 넣고 현재 위치를 방문 표시 한다.
4. bfs를 실행한다. 이때 이동할 범위가 방문 리스트의 범위를 초과하지 않도록 주의한다.
5. 현재 위치가 k에 도달했을 경우 이동한 횟수를 출력해 준다.

 

참고 사항

if문을 실행할때 이동할 위치가 0이상 10만 이하인지를 먼저 체크해 줘야 나처럼 indexError가 나지 않는다.

(if문의 and 비교 연산자 : 앞의 식이 False일 경우 뒤의 식은 체크 자체를 안함)

 

 

정답 코드

제출 코드

from collections import deque

v = [False] * 100001
n, k = map(int, input().split())
dist = (-1, 1)


def bfs(index):
    q = deque([index])
    v[index[0]] = True
    while q:
        x, cnt = q.popleft()
        if x == k:
            return cnt
        elif x < k:
            x1, x2, x3 = x + dist[0], x + dist[1], x * 2
            if 0 <= x1 < 100001 and not v[x1]:
                v[x1] = True
                q.append((x1, cnt + 1))
            if 0 <= x2 < 100001 and not v[x2]:
                v[x2] = True
                q.append((x2, cnt + 1))
            if 0 <= x3 < 100001 and not v[x3]:
                v[x3] = True
                q.append((x3, cnt + 1))
        else:
            x1 = x + dist[0]
            if not v[x1] and 0 <= x1 < 100001:
                q.append((x1, cnt + 1))


print(bfs((n, 0)))

 

최적화 코드

from collections import deque


def bfs(n, k):
    v = [False] * 100001
    q = deque([(n, 0)])
    v[n] = True
    while q:
        x, cnt = q.popleft()
        if x == k:
            return cnt
        for nx in (x - 1, x + 1, x * 2):
            if 0 <= nx < 100001 and not v[nx]:
                v[nx] = True
                q.append((nx, cnt + 1))


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