[백준] 12851번: 숨바꼭질 2 - Python

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

12851번: 숨바꼭질 2

아이디어

•  수빈이의 시작점을 시작으로 bfs
•  x-1, x+1, 2*x 이 3가지 방향으로 이어지는 그래프로 생각
• 방문했던 수는 방문처리를 해주어 탐색하지 않기
• 몇번째 층인지 확인은 방문 처리와 동시에 이루어짐
• 전 요소의 방문 인덱스에 +1한 값을 현재 요소의 방문 인덱스에 저장
• 동생의 위치에 도착하는 경우가 발생하면 그 요소의 층을 따로 저장
• 다음 층 탐색을 하기 전까지 목표 지점에 도착하는 경우가 있으면  +1

---

자료구조

• 방문 : int[]
• Queue(BFS)

---

코드구현

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

n, k = map(int, input().split())

chk = [0]*100001
cnt = 0
q = deque([n])
min_step = 10000

while q:
    tn = q.popleft()
    if chk[tn] > min_step: # 최소층 이후의 층은 탐색 할 필요가 없음
        break
    if tn == k: # 목적지에 도착하는 최소층 개수 구하기
        if chk[k] <= min_step: 
            min_step = chk[k]
            cnt += 1

    for i in (tn-1, tn+1, tn*2):
        if 1<=i and i<=100000 and (chk[i] == 0): # 
            chk[i] = chk[tn] + 1
            q.append(i)
        elif i == k: # 목적지가 또 나오면 그대로 넣기
            q.append(i)

print(min_step)
print(cnt)

결과

틀린 원인

내 머리로는 잘 떠오르지 않아 알고리즘 박사한테 물어봤다,.

이런 힌트를 받게 되는데..

 

부가 설명을 하자면 한 노드에 접근하는 방식이 +로 접근할 때랑 -로 접근할 때 *로 접근할 때가 다 다른 경우라 같은 깊이에서 같은 수에 접근하는 상황이면 이 노드도 큐에 넣어줘야 한다.

 

위 코드는 그냥 방문을 했다면 무시하는 코드로 진행되어 위와 같은 상황이 다 적용이 되지 않는다.

 

해결 방안은 방문 리스트의 값이 0이 아닌데 그 값이 현재 깊이와 같은 경우에도 append를 해주면 된다.

 

정답 코드

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

n, k = map(int, input().split())

chk = [0]*100001
cnt = 0
q = deque([n])
min_step = 100000

while q:
    tn = q.popleft()
    if chk[tn] > min_step:
        break
    if tn == k:
        if chk[k] <= min_step: 
            min_step = chk[k]
            cnt += 1

    for i in (tn-1, tn+1, tn*2):
        if 0<=i and i<=100000:
            if (chk[i] == 0):
                chk[i] = chk[tn] + 1
                q.append(i)
            elif(chk[i] == chk[tn] + 1): #다른 곳에서도 올 수 있으니
                q.append(i)


print(min_step)
print(cnt)

맞았다~!

마무리

• BFS 개념과 구현에 대한 부분은 어느정도 익힌 것 같음
• 하지만 그 안에서 문제에서 원하는 부분을 위한 로직을 끼워넣는 스킬이 아직 많이 부족한듯