๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์—ฐ๊ฒฐ ์š”์†Œ์˜ ๊ฐœ์ˆ˜1

[Java] BOJ 11724 ์—ฐ๊ฒฐ ์š”์†Œ์˜ ๊ฐœ์ˆ˜ ๋ฌธ์ œ ๋ฌธ์ œ ๋งํฌ https://www.acmicpc.net/problem/11724๋ฐฉํ–ฅ ์—†๋Š” ๊ทธ๋ž˜ํ”„๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์—ฐ๊ฒฐ ์š”์†Œ (Connected Component)์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.์ฒซ์งธ ์ค„์— ์ •์ ์˜ ๊ฐœ์ˆ˜ N๊ณผ ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ M์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ M๊ฐœ์˜ ์ค„์— ๊ฐ„์„ ์˜ ์–‘ ๋์  u์™€ v๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 ≤ u, v ≤ N, u ≠ v) ๊ฐ™์€ ๊ฐ„์„ ์€ ํ•œ ๋ฒˆ๋งŒ ์ฃผ์–ด์ง„๋‹ค. ์ฒซ์งธ ์ค„์— ์—ฐ๊ฒฐ ์š”์†Œ์˜ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ์•„์ด๋””์–ด๋…ธ๋“œ๋ฅผ ์ž…๋ ฅ๋ฐ›์„๋•Œ๋งˆ๋‹ค ArrayList๋กœ ์„œ๋กœ ๋…ธ๋“œ๋ฅผ ์—ฐ๊ฒฐํ•œ๋‹ค.for๋ฌธ์„ ์‚ฌ์šฉํ•˜์—ฌ 1๋ถ€ํ„ฐ N๊นŒ์ง€์˜ ๋…ธ๋“œ๋ฅผ ๋Œ๋ฉด์„œ ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ๋…ธ๋“œ๋ฉด ํ•ด๋‹น ๋…ธ๋“œ๋กœ BFS๋ฅผ ๋Œ๋ฆฐ๋‹ค.๊ทธ๋ฆฌ๊ณ  BFS๋ฅผ ์ด์šฉํ•˜์—ฌ ์ž…๋ ฅ๋“ค์–ด์˜จ ๋…ธ๋“œ๋ฅผ .. 2024. 8. 13.

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