[백준알고리즘/1697번/파이썬] 숨바꼭질

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

문제: 1초마다 해당 위치(X)에서 (X-1,X+1,X*2) 로 이동할 수 있을 때, 주어진 값(K) 까지 도달하는데 몇초가 걸리는지 구하는 문제입니다.

 

풀이 방법: BFS를 통해 문제를 해결하였습니다.

 

풀이 설명:

그래프 상하좌우 탐색에서 영감을 받아 해당 위치에서 이동할 수 있는 방향을 지정한 후(pos배열), 해당 점들을 방문하여 횟수를 저장하였습니다.

이때, 해당 값들에 접근하는 방식을 BFS를 통해 풀어냈습니다.

 

pos = [idx-1,idx+1,idx*2]

또한, queue에서 popleft()를 통해 값을 꺼내줌으로써 매 초마다 접근할 수 있는 점들을 순차적으로 탐색할 수 있게 설정하였습니다.

idx,cnt = queue.popleft()

풀이 코드:

import sys
from collections import deque

Max = 10 ** 5

n,k = map(int,sys.stdin.readline().split())

visitedCnt = [0]*(Max+1)

def bfs():
    queue = deque()
    queue.append([n,0])

    while queue:
        idx,cnt = queue.popleft()
        if(idx == k):
            print(cnt)
            break

        pos = [idx-1,idx+1,idx*2]

        for i in pos:
            if 0 <= i <= Max and not visitedCnt[i]:
                visitedCnt[i] = visitedCnt[idx] + 1
                queue.append([i,visitedCnt[i]])
bfs()

 

틀렸던 코드:

import sys
from collections import deque

Max = 10 ** 5

n,k = map(int,sys.stdin.readline().split())

visitedCnt = [0]*(Max)

def bfs():
    queue = deque()
    queue.append([n,0])

    while queue:
        idx,cnt = queue.popleft()
        if(idx == k):
            print(cnt)
            break

        pos = [idx-1,idx+1,idx*2]

        for i in pos:
            if 0<= i <= Max:
                visitedCnt[i] = cnt + 1
                queue.append([i,visitedCnt[i]])

bfs()

첫번째로, 최대 입력 값이 10만 이기 때문에 Max 변수에 해당 값을 저장해주었습니다.

근데, 배열 선언하는 부분에서 기초적인 실수를 했습니다. bfs함수에서 배열에 접근할 때, value = 5 라면 배열 index = 4 인 부분에 값을 저장하지 않고 index=5에 값을 저장하도록 코드를 구현하였습니다.

근데..

visitedCnt = [0]*(Max)

배열 크기를 Max+1 이 아닌 Max로 선언하여 IndexError가 발생하였습니다. value = Max 일 때, 에러가 발생한 것이죠.

정말 기초가 얼마나 중요한지 새삼 깨닫는 시간이었습니다..

 

또한, 방문했던 위치에 대하여 방문 여부를 확인 해주지 않아 큐에 너무 많은 값들이 담겨 '메모리 초과'가 발생하였습니다. 방문 여부 처리는 bfs의 기초라고 할 수 있는데 정답을 출력하는 것에만 매몰되어버려서 놓친 것이죠.

(즉, 매 초마다 방문할 수 있는 위치를 순차적으로 접근하기 때문에 값에 도달한 순간의 시간이 최소 값이기 때문에 방문 여부를 적용할 수 있었습니다.)

<틀렸던 코드>

for i in pos:
    if 0<= i <= Max:
        visitedCnt[i] = cnt + 1
        queue.append([i,visitedCnt[i]])

<정답 코드>

for i in pos:
    if 0 <= i <= Max and not visitedCnt[i]:
        visitedCnt[i] = visitedCnt[idx] + 1
        queue.append([i, visitedCnt[i]])

 

단순 bfs 문제라 생각해 엄청 간단하게 풀 수 있을줄 알았지만, 메모리 초과와 기초적인 실수들로 인한 IndexError로 인해 엄청나게 고생했던 문제입니다.(심지어 짜증마저 났던..)

하지만, 원인을 알고나서는 해당 원인을 미처 고려하지 못했던 제 부족함을 알 수 있게 되었습니다.

 

메모리 초과 부분은 제가 부족했던 점과 함께 별도로 좀 더 자세히 포스팅하도록 하겠습니다.