[Python] 1697번 숨바꼭질

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

1697번: 숨바꼭질

---

 

22/08/29

 

이 문제는 BFS를 익히는 데에 있어서 정말 좋은 문제이다.(만약 BFS 알고리즘을 배우지 않았다면 당장 배우고 오는 것을 추천한다)

 

클래스 3에도 있던 문제이기도 했고, 이전부터 계속 풀어봐야지 풀어봐야지 하고 생각하고 있었는데 까먹었었다.

 

그러다가 최근에 "클래스에서 못 풀어본 문제를 풀어보자"라고 다짐해서 계속 클래스 문제들을 밀고 있다가 이 문제를 다시 발견했다.

 

이 문제의 특별한 점은, 시리즈 문제라서 이 문제를 푼다면 약간의 수정과 아이디어 추가 만으로 나머지 문제들을 덤으로 풀 수 있다는 것이다.(날먹 ㄱㄴ)

 

---

초반 접근 방법:

 

 

처음부터 BFS 문제라는 것을 알고 있었기 때문에 BFS로 접근했다.

 

근데 알고리즘 공부를 위해서 "왜 BFS로 접근해야만 하는가"를 다시금 생각해봤다.

 

간단하게 생각을 해봤는데, 상식적으로 DFS를 하는 거면 그래프의 넓이가 유한해야 가능하다.

 

왜냐하면 DFS는 쉽게 표현하자면 깊숙히 찔렀다가 빼고, 다른데 찔렀다가 빼고, 또 다른 곳 찔렀다가 빼는 형식으로 탐색이 진행되는데, 그래프 모양이 지금처럼 어디로든 계속 뻗어나갈 수 있는 형태라면 깊숙이 찌르는 데에 한계가 생기기 때문이다.

 

이런 식으로 내 나름대로의 합리화를 진행하고 접근을 시작했다.

 

맨 처음에는 생각 없이 그냥 BFS니깐 단순히 큐에다가 방문해야 할 노드를 3개 넣어야지라고 생각했다.

 

근데 방문처리를 할 리스트나 set조차 만들지 않고 그냥 큐에다가 노드만 계속 넣었더니 메모리 초과가 나버렸다.

(더보기를 누르면 틀린 코드를 확인할 수 있다.)

# 1697번 숨바꼭질
# 그래프 이론, 그래프 탐색, BFS
'''
접근 방법:
BFS
'''
from collections import deque
N, K = map(int, input().split())

def BFS(K, start):
    queue = deque([(start, 0)]) # 위치와 시간
    while queue:
        pos, time = queue.popleft()
        if pos == K:
            print(time)
            break
        else:
            queue.append((pos+1, time+1))
            queue.append((pos-1, time+1))
            queue.append((2*pos, time+1))

BFS(K, N)

---

두 번째 접근 방법:

 

 

이후 조금 생각해보니 "저런 식으로 하면 당연히 메모리 초과가 나겠구나"라고 느꼈다.

 

한번 원소를 꺼내고 아니면 3개씩 추가가 되는 건데, 그러면 3의 지수승으로 큐의 길이가 늘어나는 꼴이 돼버리기 때문이다.

 

 그렇다면, 효과적으로 큐를 줄이려면 방문처리를 해줘야 겠구나... 라고 생각해서, 두 번째로 풀 때는 이미 방문한 곳은 set에다가 넣어서 다시 방문하지 않도록 구현해주었다.

 

근데 이게 왠걸, 또 메모리 초과가 나버렸다.

(더보기를 누르면 틀린 코드를 확인할 수 있다.)

# 1697번 숨바꼭질
# 그래프 이론, 그래프 탐색, BFS
'''
접근 방법:
BFS
'''
from collections import deque
N, K = map(int, input().split())

def BFS(K, start):
    queue = deque([(start, 0)])
    visited = set()
    while queue:
        pos, time = queue.popleft()
        visited.add(pos)
        if pos == K:
            print(time)
            break
        else:
            if pos+1 not in visited:
                queue.append((pos+1, time+1))
            if pos-1 not in visited:
                queue.append((pos-1, time+1))
            if 2*pos not in visited:
                queue.append((2*pos, time+1))

BFS(K, N)

---

세 번째 접근 방법:

 

 

이렇게 했는데도 메모리 초과가 난 거라면, 중간에 가지치기를 해야 한다고 생각했다.

 

방문하다가 내가 가고자 하는 목적지를 넘어서 간다면 뒤로 되돌아 가는 게 더 손해라고 생각이 들었다.

 

때문에 아래와 같이 코드를 작성했는데,(더보기를 누르면 확인 가능) 이번엔 틀렸습니다를 받았다.

# 1697번 숨바꼭질
# 그래프 이론, 그래프 탐색, BFS
'''
접근 방법:
BFS
'''
from collections import deque
N, K = map(int, input().split())

def BFS(K, start):
    queue = deque([(start, 0)])
    visited = set([start])
    while queue:
        pos, time = queue.popleft()
        visited.add(pos)
        if pos > K+1:
            continue
        if pos == K:
            print(time)
            break
        else:
            if pos+1 not in visited:
                queue.append((pos+1, time+1))
            if pos-1 not in visited:
                queue.append((pos-1, time+1))
            if 2*pos not in visited:
                queue.append((2*pos, time+1))

BFS(K, N)

 

이후에 내가 가지치기를 잘못 접근하고 있었다는 점을 깨달았다.

 

넘어가면 손해인 건 맞는데, 그 지점을 잘못 설정한 것이었다.

---

마지막 접근 방법:

 

 

이후 곰곰히 생각해봤다.

 

게시판의 반례들을 보니, 예를 들어 시작점이 50이고 도착점이 5인 경우처럼, 시작점보다 도착점이 더 작은 경우는 항상 최단 경로가 하나밖에 없다는 사실을 깨달았다.

 

문제에서 주어지기로는 시작점과 도착점은 항상 음이 아닌 정수라고 했고, 때문에 자기 위치의 2배가 되는 곳이나 자기 위치보다 +1된 곳은 항상 자기 위치보다 더 큰 곳에 위치해 있어서, 자기 위치보다 작은 곳으로 가려면 항상 -1로 가는 간선을 택할 수밖에 없다.

 

이러한 이유 때문에 시작점보다 도착점이 더 작은 숫자인 경우 최단 경로는 항상 정해져있고, 그 경로로 갈 때 드는 시간은 그냥 (도착점 - 시작점)로 구할 수 있다.

 

이렇게 가지치기를 크게 하나 더 해주니, 넘어가면 손해인 지점을 설정하는 것도 쉽게 보였다.

 

도착점과 시작점 사이의 거리가 있을텐데, 그 거리를 k라고 하면, (k + 도착점)을 넘어가는 지점의 경우, 도착점으로 다시 되돌아가려면 위에서 언급한 것처럼 k만큼 더 시간이 소요된다.(큰 곳에서 작은 곳으로 가려면 그냥 그 거리만큼 시간이 걸리기 때문임)

 

때문에 이 지점을 넘어가면 따지지 않고 그냥 넘기기로 했고, 그렇게 코드를 짰더니 시간 내에 통과했다.

 

---

아래는 그렇게 접근했던 나의 코드이다. python3로 제출했다. 더보기를 누르면 확인할 수 있다.

# 1697번 숨바꼭질
# 그래프 이론, 그래프 탐색, BFS
'''
접근 방법:
BFS
'''
from collections import deque
N, K = map(int, input().split())

def BFS(K, start):
    if start >= K:
        print(start-K)
        return
    queue = deque([(start, 0)])
    visited = set([start])
    while queue:
        pos, time = queue.popleft()
        visited.add(pos)
        if pos > K + K-start:
            continue
        if pos == K:
            print(time)
            break
        else:
            if pos+1 not in visited:
                queue.append((pos+1, time+1))
            if pos-1 not in visited:
                queue.append((pos-1, time+1))
            if 2*pos not in visited:
                queue.append((2*pos, time+1))

BFS(K, N)