4월25일 - BFS, 파이썬 범위 만족시키기 & 계산 결과들 활용

[BFS] 특정 노드와의 최소 거리 구하는 법

개요

어떤 노드에 도달하기까지의 최소 거리를 구하는 문제를 풀 때

BFS를 이용하면 쉽게 풀어낼 수 있다.

 

나는 개념이 안잡힌 상태에서 항상 해당 노드까지 도달하는 최소 거리를 어떻게 저장해서

필요할 때 꺼내 쓸 수 있을까 고민을 많이 했었는데

ex) 배열에 따로 저장? dict 사용? 아니면 우선순위 큐 처럼 큐에 같이 저장?

 

제일 정석적인 방법은 범위에 해당하지 않는 낮은 값으로 초기화된 특정 길이의 리스트를 만들고

arr = [0] * MAX  # MAX: 보통 노드가 될 수 있는 최대값 + 1이 된다.

해당 노드에 맞는 인덱스로 그 위치에 최소거리에 대한 값을 저장하는 방법이다.

물론 이 방법은 노드가 숫자로 이루어져 있을 때 사용하기 좋다.

 

설명을 돕기 위해 문제를 가져왔다.

 

문제

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

1697번: 숨바꼭질

대표적인 BFS 문제다. 매우 쉬운 편에 속한다고한다.

 

만약, 5에서 시작해 12에 도달할 때 까지의 시간을 구한다고 하면

위의 과정을 거치게 되는데

세가지 계산에 대해 큐에 저장하면서 해당 값들에 대해 계속 세가지 계산으로 구하는걸 반복하면 된다.

 

계산한 결과가 문제의 조건인 0 이상 100000이하인걸 충족시키고 

위에서 만들었던 arr에서의 최소거리가 0으로 되어 있으면 이전 거리에서의 +1을 해준걸 해당 위치에 저장하면 되겠다.

 

풀이를 코드로 나타내면 다음과 같다. 

 

코드

from collections import deque

N, K = map(int, input().split())
distance = [0] * 100001

queue = deque([N])
while queue:
  v = queue.popleft()
  if v == K:
    print(distance[v])
    break
  for i in (v-1, v+1, v*2):
    if 0 <= i <= 100000 and distance[i] == 0:
      distance[i] = distance[v] + 1
      queue.append(i)

최소거리 0으로 초기화해놓은 distance에 N에서 처음 도달하는 노드에 대한 거리들을 저장하고

queue에 추가했던 계산 결과 값이 K와 같으면 해당 값으로 distance에서 최소거리를 찾는 방법이다. 

간단하면서도 효과적으로 해당 문제를 풀 수 있는 방법이니 머릿속에 박자

 

파이썬 문법

if x < target < y

x, result = 5, False
if 4 < x < 6:
    result = True
print(result)  # True

위 문제를 풀며 처음 알게된 if문 사용 방법인데, 보고나서 이게 된다고? 싶어서 진짜 깜짝 놀랐다.

왜 파이썬 파이썬 하는지 인정할만하다. 

이래서 개발 전공이 아닌 사람들이 쓰기 좋다고 하는구나

덕분에 나도 자주 애용할듯

 

for target in (x, y, z)

n = 5
for i in (n-1, n+1, n+2):
    print(i, end=' ')  # 4 6 7

마찬가지로 위 문제를 풀며 알게된 for문 사용방법이다.

항상 range를 같이 쓰며 범위를 돌거나, list로 내부 요소들을 돌리며 사용했는데

특정 계산식을 나열한 후 그 결과들에 대해서도 하나씩 꺼내쓸 수 있다는 걸 알았다.

 

이 방법을 알기 전에는

for i in (v-1, v+1, v*2):
  if 0 <= i <= 100000 and distance[i] == 0:
    print(i)

위 코드를

n1 = v-1
n2 = v+1
n3 = v*2
if 0 <= n1 <= 100000 and distance[i] == 0:
  print(n1)
if 0 <= n2 <= 100000 and distance[i] == 0:
  print(n2)
if 0 <= n3 <= 100000 and distance[i] == 0:
  print(n3)

이렇게 사용했었으니 알게됐으니 충격을 받을만 했다.

 

후기

꽤 오랜만에 TIL을 쓰게 됐는데 그동안 아무것도 안하진 않고 

계속 알고리즘 문제를 푸는중이다. 

매일 새롭게 배울게 배울게 있다면 감사히 TIL을 쓰겠지만

 

프로젝트하면서 느꼈듯, 매일매일 배우기만 한다면 활용할 시간이 부족하고

활용하는 단계에서는 새로 배울 시간이 부족하다. 그 밸런스를 맞추면 좋겠지만..

 

그리고 어떤 주제에 대해 알게되서 포스팅을 할 때 굳이 TIL을 앞에 달게 되면

다른 사람이 정보를 찾을 때 방해가 될 것 같고 시리즈별로 주르륵 정리해놓기에도 보기 안좋다.

 

그런 이유로 오늘처럼 거창하게 한 주제로 포스팅할 거리 정도는 안되지만 

오늘 하루동안 알게된 새로운 지식 정도라면 TIL로 작성할 예정이다. 

 

이것도 그때그때 마음에 따라 달라질듯