Algorithm/DFS&BFS

1240๋ฒˆ/DFS ๋…ธ๋“œ์‚ฌ์ด๊ฑฐ๋ฆฌ/ํŒŒ์ด์ฌ

์ •ํ˜ธ๋‚˜ 2024. 9. 28. 18:39

๐Ÿ“• ๋ฌธ์ œ

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

 

๐Ÿ“—์‹คํ–‰๊ฒฐ๊ณผ

 

 

๐Ÿ“„  ํ’€์ด


๋ฆฌ์ŠคํŠธ ์ƒ์„ฑ ๋น„๊ต

https://m.blog.naver.com/wjddudwo209/221253421426

 

python [[]] vs [[] for _ in range(n)]

 

blog.naver.com

 

๐Ÿ’ป ๋‚ด ์ฝ”๋“œ

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

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

graph = [[] for i in range(n+1)]

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

# ์ธ์ ‘๋…ธ ํ™•์ธํ•˜๊ธฐ 
def dfs(x):
    # x์˜ ์ธ์ ‘ ๋…ธ๋“œ๋“ค ํ•˜๋‚˜์”ฉ ํ™•์ธ
    for data in graph[x]:
        y = data[0]
        # x์—์„œ y๋กœ ๊ฐ€๋Š” ๊ฐ„์„  ๋น„์šฉ
        cost = data[1]

        # ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ๋…ธ๋“œ๋ผ๋ฉด
        if not visited[y]:
            # ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌ
            visited[y] = True
            distance[y] = distance[x] + cost
            dfs(y)

for i in range(m):
    x, y = map(int, input().split())

    # ๋ฐฉ๋ฌธ ์—ฌ๋ถ€ ๋ฐ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ ํ…Œ์ด๋ธ” ์ดˆ๊ธฐํ™”
    visited = [False] * (n+1)
    distance = [-1] * (n+1)
    
    visited[x] = True
    distance[x] = 0
    dfs(x)
    print(distance[y])

 

๐Ÿ’ป ๋‹ต์•ˆ

  //

 

โ˜บ๏ธ ๋‚ด ์ฝ”๋“œ์—์„œ ๋ณด์™„ํ•ด์•ผ ํ•  ์ 

 

 

๐Ÿ˜‰ ์ฐธ๊ณ 

 

 

 

https://blog.naver.com/wjavmtngkr1/223202285334

 

๋ฐฑ์ค€ 1240 ๋…ธ๋“œ์‚ฌ์ด์˜ ๊ฑฐ๋ฆฌ ( dfs ๋ฌธ์ œ )

https://www.acmicpc.net/problem/1240 dfs ๋Š” ์ธ์ ‘๋…ธ๋“œ๋“ค์„ ํ™•์ธํ•˜๊ณ  , ์ธ์ ‘ํ•œ ๋…ธ๋“œ๊ฐ€ ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ๋…ธ๋“œ...

blog.naver.com