[BOJ] 17471 ๊ฒ๋ฆฌ๋งจ๋๋ง - Java
https://www.acmicpc.net/problem/17471 17471๋ฒ: ๊ฒ๋ฆฌ๋งจ๋๋ง ์ ๊ฑฐ๊ตฌ๋ฅผ [1, 4], [2, 3, 5, 6]์ผ๋ก ๋๋๋ฉด ๊ฐ ์ ๊ฑฐ๊ตฌ์ ์ธ๊ตฌ๋ 9, 8์ด ๋๋ค. ์ธ๊ตฌ ์ฐจ์ด๋ 1์ด๊ณ , ์ด ๊ฐ๋ณด๋ค ๋ ์์ ๊ฐ์ผ๋ก ์ ๊ฑฐ๊ตฌ๋ฅผ ๋๋ ์๋ ์๋ค. www.acmicpc.net 1. ๋ฌธ์ ์์ฝ 1๋ฒ~N๋ฒ๊น์ง N๊ฐ์ ๊ตฌ์ญ์ผ๋ก ๋๋์ด์ ธ ์๋ค. ๊ตฌ์ญ์ 2๊ฐ์ ์ ๊ฑฐ๊ตฌ๋ก ๋๋์ด์ผ ํ๊ณ , ๊ฐ ๊ตฌ์ญ์ ๋ ์ ๊ฑฐ๊ตฌ ์ค ํ๋์ ํฌํจ๋์ด์ผ ํ๋ค. ํ ์ ๊ฑฐ๊ตฌ์ ํฌํจ๋ ๊ตฌ์ญ๋ค์ ๋ชจ๋ ์ฐ๊ฒฐ๋์ด ์์ด์ผ ํ๋ค. ์ธ์ ํ ๊ตฌ์ญ์ 0๊ฐ ์ด์์ด๋ค.(ํ ์ ๊ฑฐ๊ตฌ์ ๊ตฌ์ญ์ด 1๊ฐ๊ฐ ์์ ์๋ ์๋ค.) ๋ ์ ๊ฑฐ๊ตฌ์ ํฌํจ๋ ์ธ๊ตฌ ์์ ์ฐจ์ด์ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ค. 2. ํ์ด ๋ถ๋ถ์งํฉ + bfs๋ก ํ์๋ค. 1. ๋ถ๋ถ์งํฉ์ผ๋ก A๊ตฌ์ญ, B๊ตฌ์ญ์ ..