백준 1697 : 숨바꼭질 (파이썬)

BFS 문제이다.

부끄럽지만 계속 메모리 초과가 나서 구글링해서 올바른 해답을 찾은 문제이다.

실전에서는 이런 일이 발생하지 않도록 더 실력을 키워야겠다.

---

우선 문제가 트리 구조를 떠올리면 쉽게 풀 수 있을것이라고 생각은 했다.

어떤 입력 v 가 시작값으로 주어지면, 그 입력 v 에 대해 v - 1, v + 1, v * 2 가 v 의 자식 노드로 생겨나면서 노드의 값이 k 와 일치할 때, 그 노드가 속해있는 레벨을 구하면 되는 문제였다.

 

DFS와 BFS에 대해 얼마 전에도 포스팅 한 적이 있는데, BFS는 트리의 각 레벨에 있는 모든 노드를 queue에 넣고 앞에서부터 pop 하면서 너비 우선으로 탐색하는 방식이다.

 

여기서 처음에 아이디어를 얻은 것은, queue에 각 층의 마지막 계산값들을 넣고 그 뒤를 특정한 구분자를 append 해줘서 층이 끝났다는 것을 표시해주는 것이었다.

 

설명이 다소 길어졌는데, 코드로 구현하면 아래와 같다.

 

from collections import deque
N, K = map(int, input().split())
def bfs(n, k):
    cnt = 0
    if n == k:
        return cnt
    queue = deque()
    queue.append(cnt)
    queue.append([n])
    while queue:
        v = queue.popleft()
        if type(v) is list:
            for i in v:
                a = i - 1
                b = i + 1
                c = i * 2
                if a == K or b == K or c == K:
                    return cnt
                queue.append([a, b, c])
        else:
            cnt += 1
            queue.append(cnt)
print(bfs(N, K))

 

구분자를 cnt 라는 정수로 주고, 구분자가 검출될 때마다 그 구분자에 +1 씩 해간다.

계산을 하다가 조건에 맞는 값이 발견되는 경우, 그 구분자의 값을 리턴하면 구하려는 값과 일치하는 k 값은 구분자의 값 즉, 해당 층에 있다는 의미이다.

 

대충 아무 값이나 넣고 해 봤을 때 얼추 맞게 나오는 것 같아서 제출했는데 메모리 초과가 나버렸다...

(사실 제출할 때 맞을거라는 확신이 없으면 안 될 것 같다는 느낌은 온다)

 

너무 시간을 많이 쓰는 것 같아서 구글링을 좀 했다.

다른 사람의 해답들을 보니 visited 리스트를 만들고 계산된 값을 방문할 때 마다 visited 리스트에 누적합을 시켜주고 있었는데, 해당 구조를 보니 dp가 생각났다.

 

그래도 해답을 먼저 보니 바로 이해가 되서 그 원리로 코드를 아래와 같이 새로 작성했다.

 

from collections import deque
N, K = map(int, input().split())
def bfs(n, k):
    visited = [0] * 100001
    queue = deque()
    queue.append(n)
    while queue:
        v = queue.popleft()
        if v == k:
            return visited[v]
        position = [v - 1, v + 1, v * 2]
        for i in position:
            if i >= 0 and i <= 100000 and not visited[i]:
                visited[i] += (visited[v] + 1)
                queue.append(i)
print(bfs(N, K))

---

dfs, bfs 문제들을 풀 때 방문 목록을 활용하는 법에 더 익숙해져야겠다.