[Python] 1697번 : 숨바꼭질

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

1697번: 숨바꼭질

 

문제 3줄 요약

1. 0 부터 10만까지의 좌표에 수빈이와 동생이 숨바꼭질을 한다.

2. 수빈이는 1초에 한번, 뒤로 걷기(-1), 앞으로 걷기(+1), 순간이동(*2) 중 하나를 하여 동생을 찾는다.

3. 동생이 있는 좌표에 수빈이가 도달하는 가장 빠른 시간을 출력한다.

 

---

 

예시를 통해 문제를 접근해보자.

 

EX) 수빈 : 5, 동생 : 17 일 때,

 

왼쪽 걷기, 오른쪽 걷기, 순간이동 순으로

갈 수 있는 경우의 수를 탐색한다.

 

X 표시로 지워진 숫자들은 뭘까?

 

바로

중복으로 나온 숫자이기 때문에 지워준 것이다!

 

Depth 마다 어떤 결과값이 나오는지 확인하고 넘어가야하기 때문에

BFS로 풀어주도록 하자!

 

 

---

코드는 어렵지 않다.

기존의 짜던 BFS와 동일하게 구조를 일단 작성한다.

 

좌표와 함께 cnt라는 변수를 1씩 증가시키며 큐에 넣어줌으로써,

Depth가 몇 인지 또한 체크해준다.

 

저번 포스팅에서 다뤘던 상하좌우 탐색과 유사하게

이번엔

[-1, +1, +X] 의 리스트 값을 차례대로 더해주면

 

끝!

 

from sys import stdin
from collections import deque

def bfs(M):
    
    # cnt : 트리의 Depth 체크
    bfs_deque, cnt = deque([(M,0)]), 0

    while(len(bfs_deque) > 0):
        m, cnt = bfs_deque.popleft()

        # 수진의 좌표가 동생과 같으면 종료!
        if m == K:
            return cnt
        
        # 방문한 좌표는 제외
        if visited[m]:
            visited[m] = 0
            
            # 왼쪽, 오른쪽 걷기, 순간이동 체크
            # 최소 0, 최대 10만 이하이며 방문하지 않은 좌표인지 확인
            for move in [-1,1,m]:
                if (m+move >= 0) and (m+move <= 100000) and (visited[m+move]):
                    bfs_deque.append((m+move, cnt+1))


N, K = map(int,stdin.readline().split())
visited = [1]*(100001)
print(bfs(N))

---

 

나 숨바꼭질 잘하는데,,

 

숨바꼭질 꿀팁

술래걸리면 걍 안찾고 소파에 앉아서 티비 봐버리기.