#1697

무조건 BFS다 라는 생각을 했다. 쉽게 풀릴거라 생각했다.

하나 빠뜨린 게 있었는데 입력이 5 5로 바로 찾을 수 있는 경우 => 둘이 같은 위치에 있을 경우 0을 출력해야 하는데 그걸 확인안해서 bfs로 들어가 버렸다.

print(time if N!=M else 0)

(if 조건문으로 출력 해주는거 한 줄로 하기 - 배운거 바로 써먹음)

시간 초과 => 방문 처리를 안해줬다

예를 들어 입력 예제대로 5 17로 입력이 들어왔을 때

time = 1 -> 4, 6, 10
time = 2 -> 3, 5, 8, 5, 7, 12 ~~

5는 이미 방문했던 곳인데(아닌 걸 아는데 한번 더 확인하고) queue에 X-1, X+1, 2X 를 push까지 한다. 이 과정은 굳이 필요없으므로 방문체크 Map(visit)을 만들어서 확인했던 곳인지 아닌지 체크하고 queue에 push 한다.

근데? 틀렸습니다가 나오더라, 도저히 예외가 없는데..

첫 번째 코드

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

N, M = map(int, input().split())

visit = [0 for i in range(0, 2*M)]
# print("visit = ", visit)

time = 0
def bfs():
    global time
    queue = deque()
    queue.appendleft((N, 0))

    while(queue):
        # input()
        X, nowtime = queue.pop()
        # print("X = ", X ," time = ", nowtime)

        if X > (2 * M):
            queue.pop()
            continue

        if visit[X] == 1:
            continue
        else:
            visit[X] = 1

        if X-1 == M or X+1 == M or 2*X == M:
            time = nowtime+1
            return
        
        queue.appendleft((X-1, nowtime+1))
        queue.appendleft((X+1, nowtime+1))
        queue.appendleft((2*X, nowtime+1))
        # print("queue = ", queue)

bfs()
print(time if N!=M else 0)

if X > (2 * M):
이 코드가 문제였다. M이 최대 100000이고 X는 어떤 험난한 과정을 거쳐서 M까지 갈 지 모른다. 99999까지 갈 수도 있다.

MAX를 100000으로 바꿔주고, visit 배열의 길이도 100000으로 바꿔줬다.

두 번째 코드

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

N, M = map(int, input().split())
MAX = 100000

visit = [0 for i in range(0, MAX+1)]
# print("visit = ", visit)

time = 0
def bfs():
    global time
    queue = deque()
    queue.appendleft((N, 0))

    while(queue):
        # input()
        X, nowtime = queue.pop()
        # print("X = ", X ," time = ", nowtime)

        if X == M:
            time = nowtime
            return

        if X > MAX or visit[X] == 1:
            continue

        else:
            visit[X] = 1

        queue.appendleft((X-1, nowtime+1))
        queue.appendleft((X+1, nowtime+1))
        queue.appendleft((2*X, nowtime+1))
        # print("queue = ", queue)

bfs()
print(time if N!=M else 0)

50퍼까지 잘 가다가 런타임에러(Index)가 뜬다.

마이너스 값이 되는 경우를 체크 안해줬다. 위치는 0에서 100000 사이이다.

정답 코드

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

N, M = map(int, input().split())
MAX = 100000

visit = [0 for i in range(0, MAX+1)]
# print("visit = ", visit[100000])

def bfs():
    global time
    queue = deque()
    queue.appendleft((N, 0))

    while(queue):
        # input()
        X, nowtime = queue.pop()
        # print("X = ", X ," time = ", nowtime)

        if X == M:
            print(nowtime if N!=M else 0)
            break
        
        if 0 <= X <= MAX:
            if visit[X] == 0:
                visit[X] = 1
                queue.appendleft((X-1, nowtime+1))
                queue.appendleft((X+1, nowtime+1))
                queue.appendleft((2*X, nowtime+1))

bfs()

애초에 풀이가 틀려서 그렇지 정답 코드에서 visit map 체크하는 코드를 빼도 되려나? 싶어서 빼고 돌려봤다.

안된다.