[백준 1697번] 숨바꼭질 (python/파이썬)

그래프 탐색 문제인데 수학적으로 머리를 잘 굴려서 최대한 효율적으로 탐색해야 하는 문제였다. 계속 시간초과가 떠서 이것저것 규칙을 추가하다가 문제를 발견하고 성공했다.

 

🌼 문제 링크

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

1697번: 숨바꼭질

• 티어: 실버 I
• 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색

 

 

❗ TRIAL 1.

코드

from collections import deque

walk_left = lambda x: x-1
walk_right = lambda x: x+1
jump = lambda x:2*x

def actions(v, end):
    if v > end:
        return [walk_left]
    else:
        return [walk_left, walk_right, jump]

def bfs(start, end):
    visited = [start]
    queue = deque([(0, start)])
    while queue:
        curr_time, curr_v = queue.popleft()
        if curr_v == end:
            return curr_time
        for action in actions(curr_v, end):
            new_v = action(curr_v)
            if 0 < new_v and new_v not in visited:
                visited.append(new_v)
                queue.append((curr_time+1, new_v))

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

print(bfs(N, K))

 

틀린 원인

 

시간초과. 

 

 

❗ TRIAL 2.

코드

from collections import deque

walk_left = lambda x: x-1
walk_right = lambda x: x+1
jump = lambda x:2*x

def actions(v, end):
    if v == 0:
        return [walk_right]
    if v > end:
        return [walk_left]
    elif 2*end <= 3*v:
        return [walk_left, walk_right]
    else:
        return [walk_left, walk_right, jump]

def bfs(start, end):
    if end < start:
        return start - end
    visited = [start]
    queue = deque([(0, start)])
    while queue:
        curr_time, curr_v = queue.popleft()
        if curr_v == end:
            return curr_time
        for action in actions(curr_v, end):
            new_v = action(curr_v)
            if new_v not in visited:
                visited.append(new_v)
                queue.append((curr_time+1, new_v))

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

print(bfs(N, K))

 

수정한 부분

 

- 각 node에서 action의 갯수에 따라 그래프의 크기가 매우 늘어나기 때문에 action의 갯수를 최소화하기 위해 여러 조건을 추가함.

- 현재 위치가 0일 경우 오른쪽으로만 이동하게 하고, 순간이동(2배) 했을 때 end의 2배를 넘어가는 경우에는 jump를 하지 않도록 함.

 

틀린 원인

 

시간초과.

 

 

❗ TRIAL 3.

코드

from collections import deque

walk_left = lambda x: x-1
walk_right = lambda x: x+1
jump = lambda x:2*x

def actions(v, end):
    if v == 0:
        return [walk_right]
    else:
        return [walk_left, walk_right, jump]

def bfs(start, end):
    if end <= start:
        return start - end
    times = set()
    visited = [start]
    queue = deque([(0, start)])
    while queue:
        curr_time, curr_v = queue.popleft()
        new_time = curr_time + 1
        for action in actions(curr_v, end):
            new_v = action(curr_v)
            if new_v not in visited:
                visited.append(new_v)
                if new_v == end:
                    times.add(new_time)
                    return min(times)
                elif new_v > end:
                    times.add(new_time + new_v - end)
                else:
                    queue.append((new_time, new_v))

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

print(bfs(N, K))

 

수정한 부분

 

- 현재 위치가 end보다 오른쪽에 있는 경우, 왼쪽으로 이동하는 선택지밖에 없기 때문에 해당 경우 탐색을 종료하고 curr_v-end 만큼의 시간을 curr_time에 더한 값을 times set에 기록함. 목표값을 찾았을 때, times set의 값들과 비교하여 가장 작은 값을 return 함.

- queue에서 pop 한 값들에 대해 검사를 진행하지 않고, new_v를 구한 직후에 검사를 진행함. 즉 node를 방문한 직후에 해당 node의 값을 end와 비교한다. 이렇게 하지 않고 queue에서 pop한 다음에 검사를 진행하면, node가 end에 도달했어도 해당 depth의 node를 모두 검사한 이후에 프로그램이 종료되어 비효율적이다.

 

틀린 원인

 

시간초과. 조건을 이것저것 추가해봤지만 원인은 visited에 있었다. 나는 visited를 빈 array로 만들고, 방문한 node를 차례대로 append하고 node를 방문할 때마다 해당 node가 visited에 있는지 검사했는데, 이는 array의 모든 값을 탐색하기 때문에 O(n) 시간이 소요됨.

이렇게 하지 말고 False로 구성된 array를 만들고 방문했을 때마다 True로 바꿔주어 node를 방문할 때마다 해당 값이 True/False인지 검사하게 했어야 한다.

 

 

💡 Solution

코드

from collections import deque

walk_left = lambda x: x-1
walk_right = lambda x: x+1
jump = lambda x:2*x

def actions(v, end):
    if v == 0:
        return [walk_right]
    else:
        return [walk_left, walk_right, jump]

def bfs(start, end, visited):
    if end <= start:
        return start - end
    times = set()
    visited[start] = True
    queue = deque([(0, start)])
    while queue:
        curr_time, curr_v = queue.popleft()
        new_time = curr_time + 1
        for action in actions(curr_v, end):
            new_v = action(curr_v)
            if not visited[new_v]:
                visited[new_v] = True
                if new_v == end:
                    times.add(new_time)
                    return min(times)
                elif new_v > end:
                    times.add(new_time + new_v - end)
                else:
                    queue.append((new_time, new_v))

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

visited = [False] * (2*K)
print(bfs(N, K, visited))

 

코드 설명

• 현재 위치에서 왼쪽으로 이동/오른쪽으로 이동/순간이동(2배) 로 가는 위치들을 bfs로 탐색한다.
• 만약 현재 위치가 end 보다 오른쪽에 있으면, 왼쪽으로 이동밖에 선택지가 없기 때문에 해당 가지의 탐색을 종료하고 남은 시간을 계산하여 times set에 추가한다.
• 만약 현재 위치가 end에 도달하면 모든 탐색을 종료하고, times set의 시간들과 현재 시간을 비교해 가작 작은 값을 return한다.

 

주의할 점

• 방문여부를 담은 visited array는 v in visited로 검사하면 visited의 모든 원소를 다 검사해햐 하기 때문에 오래 걸린다. 처음에 False로 구성된 array를 선언하고 값을 변경하는 방식으로 해야 함.
• BFS에서 queue에 값을 넣기 전에 종료 여부 검사를 해야 한다. queue에서 pop 한 이후에 검사하면, 조건이 달성된 이후에도 같은 depth의 node들을 모두 방문하게 되기 때문에 비효율적이다.