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