[실버 I] 1697번. 숨바꼭질

 문제 

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

1697번: 숨바꼭질

 사용 언어 

Python3

 풀이 과정 

이 문제는 실버 I길래 그나마 쉽게 풀 수 있을 줄 알았는데 또 약간 새로운 형태의 bfs라서 당황스러웠다..!

지금까지 푼 dfs 문제들은 대부분 vector 값을 이용해서 상하좌우를 살피는 방식이었는데 이 문제는 좌, 우, *2를 살펴야 했기 때문이다.

 

그래서 혼자 visited가 아닌 dp처럼 여기까지 몇 초 걸리는지를 계산한 배열이 필요할 것 같다라고까지 생각하고 bfs 구현은 어떻게 해야할 지 모르겠어서... 구글링해서 아이디어 도움을 살짝 받았다.

 

1. 수빈이로부터 각 위치의 거리를 저장하는 배열 선언
2. 초기값을 넣고 deque 선언
3. while문 안에서 하나씩 popleft해서 걷거나 순간이동으로 이동 가능한 위치 append
4. 그 세 가지 경우는 다 같은 초만에 이동할 수 있기 때문에 for문으로 묶고 dist 값에 1초를 더함
5. 주의할 점은 위치 범위를 넘지 않았는지, 해당 노드를 처음 방문하는지(dist가 0인지) 확인하는 조건문 필요

이러한 로직으로 풀었고 맞았습니다!!

이후에 코드 개선을 해나가며 시간을 조금씩 줄인 과정을 아래에 적어보겠다.

 

 제출 답안 

# 수빈이는 걷거나 순간이동
# 걸을 땐 X +- 1
# 순간이동은 2*X 위치로
# 수빈이가 동생을 찾을 수 있는 가장 빠른 시간은?

from collections import deque
from sys import stdin
input = stdin.readline

def bfs():
    q = deque([subin])
    while True:
        current = q.popleft()

        if current == brother:
            print(dist[current])
            break

        for next in (current - 1, current + 1, current * 2):
            if 0 <= next <= 100000 and dist[next] == 0:
                dist[next] = dist[current] + 1 
                q.append(next)

if __name__ == "__main__":
    subin, brother = map(int, input().split())
    # 수빈이로부터 각 위치의 거리를 저장하는 배열
    dist = [0] * 100001
    bfs()

 

 코드 개선 

1. 먼저 while True로 했던 걸 평소 bfs대로 while q로 바꿨다.

➡ 그런데 시간은 똑같고 오히려 메모리가 늘어났다?! 이유는 모르겠지만.... 그래서 다시 True로 변경했다 ㅋㅋ

 

2. 그리고 전역 변수로 실행되던 코드를 함수 안에 넣어 지역 변수로 만들어주었다.

➡ 줄어들 것 같았는데 정말 꽤 줄어들었다!

 

3. 마지막으로  if __name__ == "__main__":  을 추가해보았는데 여기선 변화가 없었다.