백준 13549 숨바꼭질3 파이썬 풀이, 반례

난이도 : 골드5
풀이일 : 04193
https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

---

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

---

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

import sys

N, K = map(int, sys.stdin.readline().split())

def find(num):
    visited = [0] * 100000
    queue = [num]
    visited[num] = 1
    p = 0
    while p < len(queue):
        i = queue[p]
        p += 1
        di = [-1, 1, i]
        for j in range(3):
            ni = i + di[j]
            if 0 <= ni < 100001 and visited[ni] == 0:
                if j < 2:
                    visited[ni] = visited[i] + 1
                elif j == 2:
                    visited[ni] = visited[i]
                queue.append(ni)
                if ni == K:
                    return print(visited[ni]-1)
find(N)

코드 구성
1. BFS 방식으로 visited를 통해 수빈이가 방문하는 좌표에 동생이 있는지 확인
2. 시간 초과를 방지하기 위해 포인터 p 사용
3. 이동은 두배 이동 시 + i, 앞 뒤 한칸씩 이동 세 경우 di 기록
4. 순간 이동 시, 시간이 늘어나지 않으므로 걷는 경우와 분리해서 visited에 시간 기록
5. 만약 수빈이가 방문할 곳에 동생이 있다면, visited 시간 -1 출력 반환
 
틀린 이유
1. visited의 100001 번째 칸도 있어야 함
2. 순간이동이 빠르지만, 걷는 경우를 먼저 처리하여 문제 발생
3. 수빈이의 위치와 동생의 위치가 같은 경우 문제 발생

---

최종 정답

# 수빈이의 좌표와 동생의 좌표가 같다면 0 출력, 다르다면 함수 실행
# BFS 함수로 가능한 모든 좌표 visited 배열 생성 후 방문 표시
# 시간초과 방지를 위해 queue + pointer 사용 
# 시간을 덜 소모하는 순간이동을 걷기보다 우선 배치하여 먼저 방문 처리
# 순간이동과 걷기를 분리하여 visited 시간 기록
# 수빈이의 좌표가 동생과 같아지면 visited 값 -1 출력 반환

import sys

N, K = map(int, sys.stdin.readline().split())

def find(num):
    visited = [0] * 100001    # 최대 숫자 배열 생성
    queue = [num]
    visited[num] = 1
    p = 0    # 시간초과 방지 포인터 사용
    while p < len(queue):
        i = queue[p]
        p += 1
        di = [i, -1, 1]    # i 우선 이동
        for j in range(3):
            ni = i + di[j]
            if 0 <= ni < 100001 and visited[ni] == 0:
                if j > 0:    # 걷는 경우
                    visited[ni] = visited[i] + 1
                elif j == 0:    # 순간이동
                    visited[ni] = visited[i]
                queue.append(ni)
                if ni == K:
                    return print(visited[ni]-1)
if N == K:
    print(0)
else:
    find(N)

코드 변화
1. visited의 100001 번째 칸까지로 크기 조정
2. 순간이동을 걷기보다 우선 배치하여 순간이동으로 인한 방문을 먼저 처리하도록 함
3. 수빈이와 동생의 위치 비교 후 다를 때만 함수 실행

---

반례

입력	1 2	2 2	4 6	1 9
출력	0	0	1	1

---

느낀점
문제를 천천히 읽고 주어진 조건을 제대로 확인하자
오늘의 틀린 이유들은 꼼꼼하게 확인하지 못한 것들이었으니 반성하자