백준 12851 숨바꼭질2 파이썬 풀이, 반례

난이도 : 골드4
풀이일 : 05092
https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

1차 시도 오답 -> 76% 틀렸습니다

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())
visited = [100001] * 100001
count = 0
mini = 100001

queue = deque([N])
visited[N] = 1
while queue:
    i = queue.popleft()
    di = [i, -1, 1]
    if visited[i] > mini:
        continue
    for j in range(3):
        ni = i + di[j]
        if 0 <= ni < 100001 and visited[ni] >= visited[i] + 1:
            visited[ni] = visited[i] + 1
            queue.append(ni)
            if ni == K:
                count += 1
                mini = visited[ni]

print(mini-1)
print(count)

코드 구성 

• 수빈이의 좌표를 queue에 넣고 BFS 탐색
• visited[i]가 mini 보다 크다면, 유망성이 없으니 해당 좌표 탐색 중단
• 수빈이가 이동할 수 있는 좌표 3곳에 대하여, visited[ni]가 visited[i] + 1과 크거나 같으면 이동 가능
• 만약 ni가 K와 같아 동생을 찾으면, count += 1, mini 재할당

틀린 이유

• 수빈이와 동생의 좌표가 같을 때 문제 발생

---

최종 정답

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())
visited = [100001] * 100001    # 작거나 같은 경우 이동가능 하도록 최대치에서 시작
count = 0    # 최소 시간으로 도달 가능한 수
mini = 100001

if N == K:    # 수빈이와 동생 좌표가 같을 때
    print(0)
    print(1)
else:    # 수빈이와 동생 좌표가 다를 때
    queue = deque([N])
    visited[N] = 1
    while queue:
        i = queue.popleft()
        di = [i, -1, 1]
        if visited[i] > mini:    # 유망성 검사
            continue
        for j in range(3):
            ni = i + di[j]
            if 0 <= ni < 100001 and visited[ni] >= visited[i] + 1:
                visited[ni] = visited[i] + 1
                queue.append(ni)
                if ni == K:    # 동생을 찾았을 때
                    count += 1
                    mini = visited[ni]

    print(mini-1)
    print(count)

코드 변화

• N, K가 같을 때 출력 조건을 따로 지정

실행 결과

• 메모리 : 35108 KB
• 시간 : 296 ms
• 코드 길이 : 678 B

---

개선 코드

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())
visited = [100001] * 100001    # 작거나 같은 경우 이동가능 하도록 최대치에서 시작
count = 0    # 최소 시간으로 도달 가능한 수
mini = 100001

queue = deque([N])
visited[N] = 1
while queue:
    i = queue.popleft()
    di = [i, -1, 1]
    if i == K:    # 동생을 찾았을 때
        count += 1
        mini = visited[i]
    if visited[i] > mini:    # 유망성 검사
        continue
    for j in range(3):
        ni = i + di[j]
        if 0 <= ni < 100001 and visited[ni] >= visited[i] + 1:
            visited[ni] = visited[i] + 1
            queue.append(ni)

print(mini-1)
print(count)

코드 변화

• 동생을 찾았을 때 실행할 로직을 ni 찾은 후에서 i 찾은 후로 이동, N과 K가 같을 때 발생하던 문제 해결

실행 결과

• 메모리 : 35748 KB
• 시간 : 284 ms
• 코드 길이 : 541 B

---

반례

입력	5 5
출력	0 1

---

느낀점
시리즈로 이어지는 문제들을 푸는게 재밌다.
토마토도 그렇고 숨바꼭질도 그렇고, 조금씩 달라지는 조건에 따라서 생각해볼 것들이 늘어나니까 금방 풀리는 것 같다.
시리즈 푼 날은 한 문제씩 더 풀수 있도록 해야지