#12851

제일 처음 위치를 찾았을 때의 시간을 기억해두고 그 시간 동안에는 같을 때마다 cnt를 증가시켜준다. 그 시간을 지난다면(1초 뒤에 바로) return 해서 bfs 함수를 끝내면 된다.

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)]
answerCnt = 0
answerTime = 0

def bfs():
    global answerCnt
    global answerTime

    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)
            answerCnt += 1
            if answerCnt == 1:
                answerTime = nowtime
        
        if answerCnt > 0 and nowtime > answerTime:
            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()
print(answerTime if N!=M else 0)
print(answerCnt)

50퍼까지 가다가 틀렸습니다가 나온다.

입력 예시로 1 3 을 했을 때

1에서 출발하면 0, 2, 2를 queue에 넣고
0일 때 -1, 1, 0
2일 때 1, 3, 4
2일 때 1, 3, 4

따라서 정답은 시간 : 2, 개수 : 2 가 나와야 한다. 하지만 위의 코드로는 2일 때는 이미 방문했으므로 한번 더 보지 않고 시간 : 2, 개수 : 1 이 나온다.

두 번째 풀이

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)]
answerCnt = 0
answerTime = 0

def bfs():
    global answerCnt
    global answerTime

    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)
            answerCnt += 1
            if answerCnt == 1:
                answerTime = nowtime
        
        if answerCnt > 0 and nowtime > answerTime:
            break
        
        if 0 <= X <= MAX:
            if visit[X] == 0:
                if X-1 != M and X+1 != M and 2*X != M:
                    visit[X] = 1
                queue.appendleft((X-1, nowtime+1))
                queue.appendleft((X+1, nowtime+1))
                queue.appendleft((2*X, nowtime+1))

bfs()
print(answerTime if N!=M else 0)
print(answerCnt)

if X-1 != M and X+1 != M and 2*X != M:
                visit[X] = 1
                
          

visit Map 을 채우기 직전에 그 숫자로 3가지 작업을 통해 M을 만들 수 없는 경우만 방문 체크를 하게 하면 된다.

근데 이것도 아니더라.

정답 코드

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])

answerTime = -1
answerCnt = 0

def bfs():
    global answerTime
    global answerCnt

    queue = deque()
    queue.appendleft((N, 0))

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

        if X == M:
            if answerTime == -1: # 처음 찾았을 때 => 최단 시간
                answerTime = nowtime

            if answerTime == nowtime: # 또 찾았을 때, 근데 같은 시간임
                answerCnt += 1
                continue
            else :
                # 시간 더 오래 걸린거는 필요없어
                break
        
        for nx in [X-1, X+1, 2*X]:
            if 0 <= nx <= MAX and visit[nx] == 0:
                queue.appendleft((nx, nowtime+1))
        # print("queue = ", queue)

bfs()
print(answerTime if N!=M else 0)
print(answerCnt)

아래의 코드가 계속 문제였다.

if X == M:
        if answerTime == -1: # 처음 찾았을 때 => 최단 시간
            answerTime = nowtime

        if answerTime == nowtime: # 또 찾았을 때, 근데 같은 시간임
            answerCnt += 1
            continue
        else :
            # 시간 더 오래 걸린거는 필요없어
            break
            

방문 체크는 사실 큰 의미가 없었다.

왜냐하면 예를 들어 입력이 1 3 이라고 했을 때

1 -> 2 -> 3 으로 3을 제일 처음 찾았다고 해보자. X가 3이 됐을 경우에 contunue로 다시 loop를 돈다.

그럼 그 때 queue는 3만 빠진 상태인

[4, 3, 4] 가 된다. 이 때 visit[3] = 1 이다. (방문 ok)

바로 다음 loop를 돌고, X=4 차례가 되어서
queue = [8, 5, 4, 3] 이 된다.

이 다음이 바로 다시 X=3이 되는데, 이 때는 visit[1~4] 모두 1이다.

위와 똑같이 X == 3 으로 continue 로 빠지게 된다.

결론적으로 정리를 해보면, 이전에 짰던 코드들은 visit[3]이 1이어서 값을 체크하지 못했는데 바로 위의 코드에서는 그런 과정이 없다.