[백준] 1240번 노드사이의 거리 파이썬 풀이

 

1240번: 노드사이의 거리

[문제]

---

---

[코드]

import sys
from collections import deque
input = sys.stdin.readline


n, m = map(int, input().split())
tree = [[] for _ in range(n+1)] #indexing을 위해서 +1사이즈로 구성

#두노드 사이 거리를 구하는 bfs
def bfs(a, b):
    q = deque()
    q.append((a, 0))
    visited = [False] * (n+1)
    visited[a] = True
    while q:
        start, distance = q.popleft()

        if start == b:
            return distance

        for i, j in tree[start]:
            if not visited[i]:
                q.append((i, distance+j))
                visited[i] = True


for _ in range(n-1):
    a, b, distance = map(int ,input().split())
    tree[a].append((b, distance))
    tree[b].append((a, distance))

for _ in range(m):
    a, b = map(int, input().split())
    print(bfs(a, b))

---

[해설]

 

오늘 풀어볼 문제는 백준 1240번 문제로

처임에 문제의 태그가 트리문제 여서 이진트리나 이진트리 탐색 문제라고 생각해서 풀이를 시작했다

그러나 문제를 풀어가면서 단순한 bfs 문제임을 알게되었고 

 

이중리스트와 deque를 활용해서 문제를 쉽게 풀 수 있었다

 

이번 문제에서 핵심은 다음 2개이다

 

1. 어떠한 자료형태로 노드 트리를 구성할 것인가

2. bfs를 활용해서 어떻게 문제를 풀것인가 - 사실 bfs를 활용해야 한다는 생각도 핵심 중 하나

 

1. 번같은 경우 처음에는 dict를 활용해서 풀려고 했으나

그러면 데이터를 추가할 때 코드가 복잡해지고 예외처리가 늘어나서 그냥 이중 리스트로 트리를 구성했다

 

하나하나 코드로 풀어가면서 살펴보면 다음과 같다

import sys
from collections import deque
input = sys.stdin.readline


n, m = map(int, input().split())
tree = [[] for _ in range(n+1)] #indexing을 위해서 +1사이즈로 구성

우선 노드의 개수인 n과 우리가 알고 싶은 노드들의 거리의 case 수를 m으로 받는다

그리고 인덱싱하기 편하게 이중 리스트를 n + 1개 만큼 형성한다 

ex [ [ ],  [ ],  [ ], ... n+1]

 

#두노드 사이 거리를 구하는 bfs
def bfs(a, b):
    q = deque()
    q.append((a, 0))
    visited = [False] * (n+1)
    visited[a] = True
    while q:
        start, distance = q.popleft()

        if start == b:
            return distance

        for i, j in tree[start]:
            if not visited[i]:
                q.append((i, distance+j))
                visited[i] = True

문제의 핵심은 연결된 노드를 따라서 출발 - 도착 노드까지의 거리이기 때문에 bfs를 활용했다

일반적인 bfs와 같이 deque를 활용해서 처음 시작점을 추가해주고

visited 리스트릴 형성해 방문한 노드를 방문처리한다

그리고 deque가 비워질 때까지 While문을 돌면서 deque 가장 왼쪽에 위치한 튜플을 가져와서 - deque에서는 삭제

시작점을 갱신해주고 거리를 받아오는데 만약 가져온 시작점이 도착점과 같은면 함수를 종료하고 현재까지 거리를 리턴한다

거리같은 경우 아래 for문을 돌면서 매번 가져온 시작점 - start, 거리 - distance를 활용해서 tree에서 갱신된 start와 연결된 노드들 중 아직방문하지 않은 노드가 있다면 이를 다시 deque에 튜플 - 연결된 노드, 시작점 부터 현재 노드까지 거리 + 현재노드에서 연결된 노드까지의 거리를 추가해주어서 갱신해준다

이렇게 하면 우리가 원하는 위치에 도달했을 때 출발점 부터의 거리가 리턴되게 된다

 

설명이 장황하지만 쉽게 설명해서 while문을 요약하자면

처음 deque에는 시작점이 들어가고 

for 문을 돌면서 시작점과 연결된 노드와 노드까지의 거리를 추가해서 deque에 추가해준다

 

그리고 이번에는 추가된 것들 하나씩 받으면서 같은 방법으로 갱신해준다

즉, 시작점이 이번에 시작점과 연결되었던 노드로 변화하고 거기에 연결되어 있는 노드와 거리를 갱신해 주는 것이다

 

for _ in range(n-1):
    a, b, distance = map(int ,input().split())
    tree[a].append((b, distance))
    tree[b].append((a, distance))

for _ in range(m):
    a, b = map(int, input().split())
    print(bfs(a, b))

그리고 이렇게 만들어진 함수를 활용하여서 문제를 풀 수 있다

우선 for문을 활용해서 n-1 만큼 반복하면서 - 이는 문제에 나타나있다

tree의 a 노드 위치에 연결된 b와 b까지의 거리를 튜플로 추가해주고

tree의 b 노드 위치에도 a와 a까지의 거리를 튜플로 추가해준다

 

그리고 난 이후 

우리가 알고 싶은 case인  m만큼 for문을 반복하면서 

시작점과 목표지점을 a, b로 받아서 

이를 앞에서 작성한 bfs에 적용하여 이를 출력하면

 

입력받은 a부터 b까지의 거리가 출력되게 된다