1260 1
[๋ฐฑ์ค€(BOJ) / Python] 1260๋ฒˆ: DFS์™€ BFS

๋ฌธ์ œ ๋งํฌ: www.acmicpc.net/problem/1260 1260๋ฒˆ: DFS์™€ BFS ์ฒซ์งธ ์ค„์— ์ •์ ์˜ ๊ฐœ์ˆ˜ N(1 ≤ N ≤ 1,000), ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ M(1 ≤ M ≤ 10,000), ํƒ์ƒ‰์„ ์‹œ์ž‘ํ•  ์ •์ ์˜ ๋ฒˆํ˜ธ V๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ M๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ„์„ ์ด ์—ฐ๊ฒฐํ•˜๋Š” ๋‘ ์ •์ ์˜ ๋ฒˆํ˜ธ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์–ด๋–ค ๋‘ ์ •์  ์‚ฌ www.acmicpc.net ๋ฌธ์ œ ์„ค๋ช… ๋‹จ์ˆœํžˆ DFS์™€ BFS๋ฅผ ์ˆ˜ํ–‰ํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค. ์ €๋Š” (N + 1) X (N + 1) ํฌ๊ธฐ์˜ matrix๋ฅผ ์ด์šฉํ•ด ์ •์  ๊ฐ„์˜ ๊ฐ„์„ ์„ ํ‘œ์‹œํ–ˆ์Šต๋‹ˆ๋‹ค. ๋˜ํ•œ dfs๋ฅผ ํ•  ๋• ๋ฐฉ๋ฌธํ•œ ๋…ธ๋“œ๋ฅผ 1๋กœ ํ‘œํ˜„ํ•˜๊ณ  bfs๋ฅผ ํ•  ๋• 0์œผ๋กœ ํ‘œํ˜„ํ•ด์„œ visited๋ฅผ ๋”ฐ๋กœ ์ดˆ๊ธฐํ™”ํ•  ํ•„์š” ์—†์ด ๋ฐ”๋กœ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋„๋ก ํ–ˆ์Šต๋‹ˆ๋‹ค. ์†Œ์Šค์ฝ”๋“œ def dfs(v): # ๋ฐฉ๋ฌธ ๋…ธ๋“œ 1๋กœ ํ‘œํ˜„..
Algorithm/๋ฐฑ์ค€(BOJ) 2021.03.15
1
๋”๋ณด๊ธฐ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”