[백준/Python] 1240번(그래프,BFS,DFS)_노드사이의 거리

📌문제 유형

그래프, 트리, BFS, DFS (골드5)

 

📌문제

1240번: 노드사이의 거리

 

📌나의 문제풀이

- BFS

from collections import deque

n,m = map(int,input().split())

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


for _ in range(m):
    q = deque()
    start, end = map(int,input().split())
    visited = [0 for _ in range(n+1)]
    visited[start] = 1

    q.append((start,0)) 
    while q:
        s, dis = q.popleft()
        if s == end:
            print(dis)
            break

        for v, d in maps[s]:
            if visited[v] == 0:
                q.append((v,d+dis))
                visited[v] = 1

- DFS

n, m = map(int,input().split())

maps = [[] for _ in range(n+1)]

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


def dfs(x, ans):
    if x == y_:
        print(ans)
        return

    for y, d in maps[x]:
        if visited[y] == 0:
            visited[y] = 1
            dfs(y,ans + d)  # ans += d 보다는 ans값을 직접 전달해 주는 것이 답임
            # return
    
for _ in range(m):
    x_, y_ = map(int,input().split())
    visited = [0 for _ in range(n+1)]
    visited[x_] = 1
    dfs(x_,0)

 

📌 다른사람의 문제풀이

- BFS

from collections import deque

def distance(x, y):
    queue = deque()
    queue.append((x, 0))

    visited = [0 for _ in range(N+1)]
    visited[x] = 1

    while queue:
        v, d = queue.popleft()

        if v == y:
            return d

        for w, dist in graph[v]:
            if not visited[w]:
                visited[w] = 1
                queue.append((w, d+dist))


N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]

for _ in range(N-1):
    i, j, dist = map(int, input().split())

    graph[i].append((j, dist))
    graph[j].append((i, dist))

for _ in range(M):
    x, y = map(int, input().split())
    print(distance(x, y))

- DFS

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)

def DFS(start,end , check):

    global count

    if start==end:
        count=check
        return

    for i,j in Tree[start]:
        if not visit[i]:
            visit[i]=True
            DFS(i, end , check+j)

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

Tree=[ [] for _ in range(N+1) ]

for i in range(N-1):
    a,b,c=map(int,input().split())
    Tree[a].append([b,c])
    Tree[b].append([a,c])

for i in range(M):
    a,b=map(int,input().split())
    visit=[False]*(N+1)
    count=0
    visit[a]=True

    DFS(a,b , 0)
    print(count)

 

📌 리뷰 

- BFS로 (시작 위치, 합친 거리)만 deque에 넣고 진행

- DFS에서 maps[s]의 i,j 값으로 dfs 함수 다루기