[BOJ][Python]1697번 풀이

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

1697번: 숨바꼭질

from collections import deque

n,k = map(int, input().split())
q = deque([[n,0]])
visited = [False for _ in range(100001)]
visited[n] = True
while 1:
    if n == k:
        print(0)
        break
    p = q.popleft()
    a = p[0]-1
    b = p[0]+1
    c = p[0]*2
    if a == k or b == k or c == k:
        print(p[1]+1)
        break
    else:
        if a>=0 and visited[a] == False:
            q.append([a,p[1]+1])
            visited[a] = True
        if b<=100000 and visited[b] == False:
            q.append([b,p[1]+1])
            visited[b] = True
        if c<=100000 and visited[c] == False:
            q.append([c,p[1]+1])
            visited[c] = True

이 문제는 반례를 최대한 생각해내는게 중요합니다. 물론 머리가 좋으신 분들은 그런 과정없이 아 이렇게 하면 되겠구나 하고 슥슥 풀어내신 분도 있으시겠지만 저는 그렇지 않았기 때문에 저를 기준으로 말을 좀 해보겠습니다.

 

일단 해당 문제는 사용가능한 알고리즘들이 많이 있겠지만 저는 bfs로 풀어봤습니다. 예전에 미로찾기 알고리즘이 어떻게 돌아가는지 시각화해서 보여주는 영상을 봤던 적이 있어서 풀이 방법을 좀 빨리 떠올릴 수 있었던 것 같아요. 처음엔 dp랑 브루트포스 결합인가? 하고 생각도 했었습니다. 구현할 방법을 생각하지 못해서 그만두긴 했지만요.

 

bfs로 풀기로 결정을 했으면 기본적으로 해줘야 하는 건 데크나 큐 모듈을 불러오고 방문 처리용 리스트를 만드는 일이죠. 방문처리는 안할 수 없는게 bfs 알고리즘 특성상 갔던 곳을 또 가는 일이 매우 많기 때문에 꼭 해줘야 합니다. 그 다음에는 기본적인 bfs 문제를 풀듯이 쭉쭉 써주신 다음에 몇가지 조건을 정해줍시다. 먼저 n과 k가 같을 가능성을 따져야 합니다. 문제에서 다르다는 얘기가 없기 때문에 같을 수도 있다는 가능성을 염두에 두고 해당 경우를 처리할 방법을 생각해봐야 합니다. 만일 따로 해주지 않는다면 n과 k가 같음에도 결과가 2가 될 거에요. 따라서 같을 경우 0을 출력하고 반복문을 멈추는 코드를 넣어줍시다.

 

저는 데크에 넣는 원소를 [위치, 걸린 시간]의 리스트로 집어넣었는데요. 그 이유는 포지션마다 도달하는데 걸린 시간이 다르기 때문입니다. 다른 분들은 이 부분을 어떻게 처리하셨을지 모르겠는데 저는 뭐가 제일 먼저 도달할지 모르니까 걸린 시간도 함께 사용해서 3가지 중에서 k와 같아지는게 나오면 걸린 시간+1을 출력하는 방법으로 해결했습니다. 그 밑에 있는 조건문은 각각의 경우에 가능한 범위와 방문 여부를 만족하면 데크에 추가하는 방법으로 인덱스 에러를 방지하고 사용 메모리를 줄여봤습니다. 처음에는 방문 처리를 안했었는데 한 번 반복문이 돌 때 마다 3^n만큼 원소가 늘어나기 때문에 금방 메모리 한계에 도달해서 방문 처리는 꼭 해주셔야 합니다.