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

156841

[BOJ] 15684 : ์‚ฌ๋‹ค๋ฆฌ ์กฐ์ž‘ ๋ฌธ์ œ ๋งํฌ https://www.acmicpc.net/problem/15684 15684๋ฒˆ: ์‚ฌ๋‹ค๋ฆฌ ์กฐ์ž‘ ์‚ฌ๋‹ค๋ฆฌ ๊ฒŒ์ž„์€ N๊ฐœ์˜ ์„ธ๋กœ์„ ๊ณผ M๊ฐœ์˜ ๊ฐ€๋กœ์„ ์œผ๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ์ธ์ ‘ํ•œ ์„ธ๋กœ์„  ์‚ฌ์ด์—๋Š” ๊ฐ€๋กœ์„ ์„ ๋†“์„ ์ˆ˜ ์žˆ๋Š”๋ฐ, ๊ฐ๊ฐ์˜ ์„ธ๋กœ์„ ๋งˆ๋‹ค ๊ฐ€๋กœ์„ ์„ ๋†“์„ ์ˆ˜ ์žˆ๋Š” ์œ„์น˜์˜ ๊ฐœ์ˆ˜๋Š” H์ด๊ณ , ๋ชจ๋“  ์„ธ๋กœ์„  www.acmicpc.net ๋ฐฑํŠธ๋ž˜ํ‚น์œผ๋กœ ์™„์ „ํƒ์ƒ‰ํ•˜๊ธฐ. ํ’€์ด ๊ธฐ์กด์˜ ์‚ฌ๋‹ค๋ฆฌ์— 3๊ฐœ ์ดํ•˜์˜ ์ƒˆ๋กœ์šด ๋‹ค๋ฆฌ๋ฅผ ๋†“์•„์„œ i๋ฒˆ ์‚ฌ๋‹ค๋ฆฌ๊ฐ’์ด i๊ฐ€ ๋‚˜์˜ค๋„๋ก ๋งŒ๋“œ๋Š” ๋ฌธ์ œ. ๋ฐฑํŠธ๋ž˜ํ‚น์„ ํ†ตํ•ด์„œ ์ƒˆ๋กœ ๋‹ค๋ฆฌ๋ฅผ ๋†“์„ ์œ„์น˜๋ฅผ ์ •ํ•œ๋‹ค. ์—ฌ๊ธฐ์„œ ๋‹ค๋ฆฌ์˜ ์—ฌ๋ถ€๋Š” is_connected ๋ฐฐ์—ด์„ ์ด์šฉํ•ด์„œ ์ €์žฅํ–ˆ๋‹ค. is_connected[๋†’์ด][๋ง‰๋Œ€ ๋ฒˆํ˜ธ1][๋ง‰๋Œ€ ๋ฒˆํ˜ธ2] ์ด๋ ‡๊ฒŒ 3์ฐจ์›๋ฐฐ์—ด๋กœ ๋งŒ๋“ค์–ด์ฃผ์—ˆ๊ณ  ๊ฐ’์ด true๋ฉด 1๋ฒˆ 2๋ฒˆ ๋ง‰๋Œ€ ์‚ฌ์ด์— ๊ฐ€๋กœ๋กœ.. 2022. 4. 14.

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