์ด๋ถ„๊ทธ๋ž˜ํ”„

    [BOJ_1707] ์ด๋ถ„๊ทธ๋ž˜ํ”„ (java)

    [BOJ_1707] ์ด๋ถ„๊ทธ๋ž˜ํ”„ (java)

    ๋ฌธ์ œ๋งํฌ https://www.acmicpc.net/problem/1707 1707๋ฒˆ: ์ด๋ถ„ ๊ทธ๋ž˜ํ”„ ์ž…๋ ฅ์€ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ๋Š”๋ฐ, ์ฒซ์งธ ์ค„์— ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜ K๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ฒซ์งธ ์ค„์—๋Š” ๊ทธ๋ž˜ํ”„์˜ ์ •์ ์˜ ๊ฐœ์ˆ˜ V์™€ ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ E๊ฐ€ ๋นˆ ์นธ์„ ์‚ฌ์ด์— www.acmicpc.net ๋ฌธ์ œ์„ค๋ช… ๋”๋ณด๊ธฐ ๋”๋ณด๊ธฐ ๋ฌธ์ œ ๊ทธ๋ž˜ํ”„์˜ ์ •์ ์˜ ์ง‘ํ•ฉ์„ ๋‘˜๋กœ ๋ถ„ํ• ํ•˜์—ฌ, ๊ฐ ์ง‘ํ•ฉ์— ์†ํ•œ ์ •์ ๋ผ๋ฆฌ๋Š” ์„œ๋กœ ์ธ์ ‘ํ•˜์ง€ ์•Š๋„๋ก ๋ถ„ํ• ํ•  ์ˆ˜ ์žˆ์„ ๋•Œ, ๊ทธ๋Ÿฌํ•œ ๊ทธ๋ž˜ํ”„๋ฅผ ํŠน๋ณ„ํžˆ ์ด๋ถ„ ๊ทธ๋ž˜ํ”„ (Bipartite Graph) ๋ผ ๋ถ€๋ฅธ๋‹ค. ๊ทธ๋ž˜ํ”„๊ฐ€ ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ด ๊ทธ๋ž˜ํ”„๊ฐ€ ์ด๋ถ„ ๊ทธ๋ž˜ํ”„์ธ์ง€ ์•„๋‹Œ์ง€ ํŒ๋ณ„ํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ž…๋ ฅ์€ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ๋Š”๋ฐ, ์ฒซ์งธ ์ค„์— ํ…Œ์Šค..