[백준][파이썬] 1697 숨바꼭질

# 문제 링크

https://www.acmicpc.net/problem/1697

# 문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

# 입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

# 출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

# 예제 입력                 # 예제 출력

5 17

4

 

 

# 예제 해설

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

 

---

# 문제 풀이

n부터 시작해서 n-1, n+1, n*2에 위치한 수들을 탐색하며 k와 일치하기까지 몇번 루프해야 하는지 세는 문제이다.

이진 트리에서 자식이 하나 더 파생되는 구조라, 무작정 모든 케이스(n-1, n+1, n*2)를 탐색하면 3의 n승 만큼 시간복잡도가 소요되어 비효율적이다! 잘 생각해보면 이미 방문했던 수는 나중에 더이상 방문할 필요 없다. 왜냐하면 가장 빠른 시간을 구하는 것이기 때문이다! 따라서 visited 배열을 선언하여 방문여부를 검사하였다.

그리고 n-1, n+1, n*2 값들이 0 <= ... <= 100000 범위를 벗어나지 않게 조건문으로 처리해 주었다.

 

틀린코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())

search = [n]
sec = 0
visited = [False] * 100001

success = True
while success :
    locations = []
    sec += 1
    for elem in search :
        if 0 <= elem + 1 <= 100000 :
            x = elem + 1
            if x == k :
                success = False
                break
            if not visited[x] :
                locations.append(x)
                visited[x] = True

        if 0 <= elem - 1 <= 100000 :
            x = elem - 1
            if x == k :
                success = False
                break
            if not visited[x] :
                locations.append(x)
                visited[x] = True

        if 0 <= elem * 2 <= 100000 :
            x = elem * 2
            if x == k :
                success = False
                break
            if not visited[x] :
                locations.append(x)
                visited[x] = True
    search = locations

print(sec)

맞았을거라 생각했는데 틀렸다. 제출 전에 범위 끝값에서도 잘 돌아가는지 확인하려고 0 0 을 테스트케이스로 넣어 돌려 보았을 때 1이 나왔고, 1 1을 테스트케이스로 넣으면 2가 나왔다. 문제에서 '수빈이는 걷거나 순간이동을 할 수 있다.' 라고 명시되어 있어서 제자리에 있는 건 불가능하고, 시작이 0일 때는 0*2 = 0 이라 1초, 시작이 1일 때는 1 + 1 - 1 = 1 이라 2초가 걸리는 구나! 하고 있었는데....

 

맞은코드

import sys
input = sys.stdin.readline

# 입력
n, k = map(int, input().split())

search = [n]                # +1, -1, *2 해야 하는 지점
sec = 0                     # 소요시간
visited = [False] * 100001  # 방문여부
success = True     


# 수빈이와 동생이 같은 위치에 있는 경우
if n == k :
    success = False

# 수빈이와 동생이 다른 위치에 있는 경우
while success :
    locations = []  # 방문할 지점
    sec += 1
    for point in search :
        if 0 <= point + 1 <= 100000 : # 범위 검사
            x = point + 1
            if x == k :
                success = False
                break
            if not visited[x] : # 방문 한 적 없으면
                locations.append(x) # 지역에 추가
                visited[x] = True   # 방문 처리

        if 0 <= point - 1 <= 100000 :
            x = point - 1
            if x == k :
                success = False
                break
            if not visited[x] :
                locations.append(x)
                visited[x] = True

        if 0 <= point * 2 <= 100000 :
            x = point * 2
            if x == k :
                success = False
                break
            if not visited[x] :
                locations.append(x)
                visited[x] = True

    search = locations  # 갱신

# 출력 처리
print(sec)

혹시? 싶어서 n과 k가 같을 때 예외 처리를 해 주니 통과되었다...

제자리 있기가 안 되는 줄 알았죠...ㅠㅠ

 

개선 코드

함수로 묶어서 반복되는 부분을 줄일 수 있다!

import sys
input = sys.stdin.readline

n, k = map(int, input().split())

search = [n]
sec = 0
visited = [False] * 100001

# 이동 처리 함수
def move(pos, nxt, locations):
    if 0 <= nxt <= 100000 and not visited[nxt]:
        if nxt == k:
            return True
        visited[nxt] = True
        locations.append(nxt)
    return False

if n == k:
    print(0)
else:
    success = True
    while success:
        locations = []
        sec += 1
        for elem in search:
            # 세 가지 이동을 함수로 처리
            if move(elem, elem + 1, locations): 
                success = False
                break
            if move(elem, elem - 1, locations): 
                success = False
                break
            if move(elem, elem * 2, locations): 
                success = False
                break
        search = locations

    print(sec)