왜 점점 멍청해지는 기분이..?

#1697번 숨바꼭질 https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

너무 쉬운 문제라 가볍게 임했다. 

 

< 틀린 코드 >

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

visited = [False]*(100001)
que = []


def solve(time, position):
    visited[position] = True
    que.append([position, time])

    while que:
        # print(que)
        p, t = que.pop(0)

        for move in [-1, +1, 2]:
            if move == 2:
                tmp = p*2
            else:
                tmp = p + move

            if 0 <= tmp <= 100000:
                if tmp == T:
                    return t+1
                else:
                    if not visited[tmp]:
                        que.append([tmp, t+1])
                        visited[tmp] = True


print(solve(0, N))

 

장렬하게 틀렸다.

 

도저히 왜 틀렸는지 모르겠다. 아직까지도 의문이다. (백준은 테스트 케이스를 추가해달라!!)

 

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

M = 10**5
dist = [0]*(M+1)


def solve(position):
    que = []
    que.append(position)

    while que:
        p = que.pop(0)
        if p == T:
            return dist[p]
        for np in [p-1, p+1, p*2]:
            if 0 <= np <= M and not dist[np]:
                dist[np] = dist[p] + 1
                que.append(np)


print(solve(N))

구글링 후 수정한 코드이다.

사실상 거의 비슷하지만 핵심은 거리를 리스트에 기록하는 형태이다.

 

기존의 코드에서 나는 시간을 카운트 하는 방식을 택했고 그래프의 탐색 깊이가 깊어질수록 수가 늘어나는 코드의 특성상 카운트 방식이 정확할거란 보장이 없는 듯 하다.

 

그래서  리스트 형태로, 위치마다 기록해주는게 더 좋은 방법이다. (약간 DP 느낌도 나고 좋죠)