[백준] 12851 숨바꼭질 2 (python 파이썬)

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

12851번: 숨바꼭질 2

---

아이디어

 

1. bfs

• 이미 숨바꼭질 1과 3을 풀어서 대충 알고 있다. x - 1, x + 1, x * 2 큐에 넣어주면서 탐색하면 됨.
• 경우의 수를 어떻게 구할지 생각만 하면 된다.

2. 경우의 수

• 쭉 탐색을 하다가 맨 처음 동생한테 도착한 시간을 저장하고
• 이후 동생한테 도착했을 때 저장해둔 시간과 같다면 경우의 수를 +1 해준다.

---

전체 코드

from collections import deque
N, K = map(int,input().split())
visited = [0] * 200001


def bfs(n):
    ans_count = 100001
    ans_way = 0

    deq = deque()
    deq.append([n, 0])
    visited[n] = 0

    while deq:
        x, count = deq.popleft()

        if count > ans_count:
            continue

        if x == K:
            if ans_count == 100001:
                ans_count = count

            if count == ans_count:
                ans_way += 1

        arr = [x - 1, x + 1, x * 2]

        for a in arr:
            if 0 <= a <= 200000 and (visited[a] == 0 or visited[a] == count + 1):
                visited[a] = count + 1
                deq.append([a,count + 1])

    return ans_count, ans_way

for ans in bfs(N):
    print(ans)

---

코드 설명

def bfs(n):
    ans_count = 100001
    ans_way = 0

    deq = deque()
    deq.append([n, 0])
    visited[n] = 0

    while deq:
        x, count = deq.popleft()

        if count > ans_count:
            continue

        if x == K:
            if ans_count == 100001:
                ans_count = count

            if count == ans_count:
                ans_way += 1

        arr = [x - 1, x + 1, x * 2]

        for a in arr:
            if 0 <= a <= 200000 and (visited[a] == 0 or visited[a] == count + 1):
                visited[a] = count + 1
                deq.append([a,count + 1])

    return ans_count, ans_way

먼저 방법의 수를 저장할 ans_way변수와 최단 시간을 저장할 ans_count를 선언해준다.

ans_count는 100000 0 입력이 들어왔을 때 나오는 시간(100000) 보다 크게 설정(100001)

그리고 visited리스트를 boolean 리스트가 아닌 int 리스트로 선언한다. 나중에 사용함.

 

기본적인 틀은 간단하다.

큐에 x + 1, x - 1, x * 2가 조건에 충족하면 큐에 넣고 탐색하는 방법이다.

주어진 범위에서 방문을 하지 않았거나, 아니면 그 위치에 최단시간으로 방문한 경우 큐에 추가해준다.

 

왜 방문 유무만 따지는 게 아니냐면, 예를 들어 1 3으로 입력이 들어왔다고 치면

1 2 3(+1 +1)

1 2 3(*2 +1) 

이렇게 총 2가지 경우가 나온다. *2와 +1 은 다른 경우이므로 이를 구분해줘야 함.

 

탐색을 하다 보면 최초로 동생에게 도착하는 경우가 생길 거다.

그럼 이때(if x == K 일 때) ans_count에 값을 업데이트하고 ans_way값을 1 증가시켜준다.

이후에는 ans_count 값이 count와 같으면 ans_way값을 1 증가시켜준다.

 

이 문제를 풀면서 정말 많이 틀렸다. 풀면서 느낀 건 엣지 케이스는 무조건 해보고 제출하기.