๋ถ๋ฅ ์ ์ฒด๋ณด๊ธฐ214 [๋ฐฑ์ค] 2437 ์ ์ธ (Python/ํ์ด์ฌ) https://www.acmicpc.net/problem/2437 2437๋ฒ: ์ ์ธ ํ๋์ ์ํ ์ ์ธ์ ์ด์ฉํ์ฌ ๋ฌผ๊ฑด์ ๋ฌด๊ฒ๋ฅผ ์ธก์ ํ๋ ค๊ณ ํ๋ค. ์ด ์ ์ธ์ ์ ํ์ ๋์๋ ๋ฌผ๊ฑด์ด๋ ์ถ๋ฅผ ์ฌ๋ ค๋๋ ์ ์๊ฐ ๋ฌ๋ ค ์๊ณ , ์ํ์ ๊ธธ์ด๋ ๊ฐ๋ค. ๋ํ, ์ ์ธ์ ํ์ชฝ์๋ ์ ์ธ์ถ๋ค๋ง ๋ www.acmicpc.net ๊ทธ๋ฆฌ๋ ๋ฌธ์ ๋ก ์ ๋ต์ฝ๋๋ฅผ ๋ณด๋ฉด ๋งค์ฐ ๋จ์ํ๋ฐ ์์ด๋์ด๋ฅผ ๋ ์ฌ๋ฆฌ๊ธฐ๊น์ง๊ฐ ๋งค์ฐ ํ๋ค๋ค. ํต์ฌ ์์ด๋์ด๋ ๋ค์๊ณผ ๊ฐ๋ค. ํ์ฌ๊น์ง ์ธก์ ๊ฐ๋ฅํ ๋ฌด๊ฒ์ ์ต๋๊ฐ์ ans๋ผ๊ณ ํ๋ฉด (1 - ans)์ ๊ฐ๋ค์ ์ธก์ ํ ์ ์๋ค. ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋ ๋ฌด๊ฒ์ถ๋ค ์ค์์ ํ๋์ ๋ฌด๊ฒ์ถ(weight)์ ์ ํํ๋ค. weight ans + 1๋ผ๋ฉด ans + 1์ ๊ฐ์ ์ธก์ ๋ถ๊ฐ๋ฅํ๋ฏ๋ก ํด๋น ๊ฐ์ด ์ ๋ต์ด ๋๋ค. ๋จ 1, 1, 1, 1 ํน.. 2022. 10. 3. [๋ฐฑ์ค] 20056 ๋ง๋ฒ์ฌ ์์ด์ ํ์ด์ด๋ณผ (Python/ํ์ด์ฌ) https://www.acmicpc.net/problem/20056 20056๋ฒ: ๋ง๋ฒ์ฌ ์์ด์ ํ์ด์ด๋ณผ ์ฒซ์งธ ์ค์ N, M, K๊ฐ ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ M๊ฐ์ ์ค์ ํ์ด์ด๋ณผ์ ์ ๋ณด๊ฐ ํ ์ค์ ํ๋์ฉ ์ฃผ์ด์ง๋ค. ํ์ด์ด๋ณผ์ ์ ๋ณด๋ ๋ค์ฏ ์ ์ ri, ci, mi, si, di๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. ์๋ก ๋ค๋ฅธ ๋ ํ์ด์ด๋ณผ์ ์์น www.acmicpc.net ํน๋ณํ ์๊ณ ๋ฆฌ์ฆ์ ํ์๋ก ํ์ง ์๋ ๊ตฌํ ๋ฌธ์ ์ด๋ค. ์ด๋ค ์๋ฃ๊ตฌ์กฐํ์ ์ด๋ป๊ฒ ์ฌ์ฉํด์ ํ์ด์ด๋ณผ์ ์ ๋ณด์ ์์น ๋ฑ์ ๋ํ๋ผ ๊ฒ์ธ๊ฐ๊ฐ ์๊ฐํ๊ธฐ ์ข ๊น๋ค๋กญ๋ค ๊ตฌํํด์ผํ ์์๋ ํฌ๊ฒ ํ์ด์ด๋ณผ์ ์ด๋ / ํ์ด์ด๋ณผ์ ๋ณํฉ๊ณผ ๋ถ์ฐ์ด๋ค. ๋จผ์ ํ์ด์ด๋ณผ์ ์ด๋์ด๋ค. ํ์ด์ด์ด๋ณผ์ ์ด๋์ ๋ฆฌ์คํธ์ ๋ด์ ํ์ด์ด๋ณผ์ ์ ๋ณด๋ฅผ ํ๋์ฉ ๊บผ๋ด์ ๋น ๋ฆฌ์คํธ๋ฅผ ์์๋ก ๊ฐ์ง N x N ๋ฐฐ์ด(๋ฆฌ.. 2022. 10. 3. [๋ฐฑ์ค] 14621 ๋๋ง ์๋๋ ์ฐ์ (Python/ํ์ด์ฌ) https://www.acmicpc.net/problem/14621 14621๋ฒ: ๋๋ง ์๋๋ ์ฐ์ ์ ๋ ฅ์ ์ฒซ์งธ ์ค์ ํ๊ต์ ์ N์ ํ๊ต๋ฅผ ์ฐ๊ฒฐํ๋ ๋๋ก์ ๊ฐ์ M์ด ์ฃผ์ด์ง๋ค. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) ๋์งธ ์ค์ ๊ฐ ํ๊ต๊ฐ ๋จ์ด ๋ํ๊ต๋ผ๋ฉด M, ์ฌ์ด ๋ํ๊ต๋ผ๋ฉด W์ด ์ฃผ์ด์ง๋ค. ๋ค์ M๊ฐ์ www.acmicpc.net 1. ๊ธฐ๋ณธ์ ์ธ MST ๋ฌธ์ ์ด๋ค. 2. ๋ํ๊ต ๋จ์ด/์ฌ์ด ์ฌ๋ถ๋ฅผ ๋์ ๋๋ฆฌ ํํ๋ก ์ ์ฅํด์ ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ์์ ๋ค์ ๊ฐ์ ์ ํ ์ ๋ค๋ฅธ ์ข ๋ฅ์ ๋ํ๊ต์ผ ๊ฒฝ์ฐ๋ง ์ ํํ๋๋ก ํ๋ค. 3. ๊ทธ ์ธ์๋ ์กฐ๊ฑด์ ๋ง์กฑํ๋ mst๊ฐ ์์ ๊ฒฝ์ฐ -1์ ์ถ๋ ฅํ๋๋ก ํด์ผ๋๋ค. import sys, os, io, atexit input = lambda: sys.stdin.read.. 2022. 10. 2. [๋ฐฑ์ค] 16724 ํผ๋ฆฌ ๋ถ๋ ์ฌ๋์ด (Python/ํ์ด์ฌ) https://www.acmicpc.net/problem/16724 16724๋ฒ: ํผ๋ฆฌ ๋ถ๋ ์ฌ๋์ด ์ฒซ ๋ฒ์งธ ์ค์ ์ง๋์ ํ์ ์๋ฅผ ๋ํ๋ด๋ N(1 ≤ N ≤ 1,000)๊ณผ ์ง๋์ ์ด์ ์๋ฅผ ๋ํ๋ด๋ M(1 ≤ M ≤ 1,000)์ด ์ฃผ์ด์ง๋ค. ๋ ๋ฒ์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ ์ง๋์ ์ ๋ณด๋ฅผ ๋ํ๋ด๋ ๊ธธ์ด๊ฐ M์ธ ๋ฌธ์์ด์ด ์ฃผ www.acmicpc.net 0. DFS / BFS (+ ์ ๋์จํ์ธ๋) ๋ฌธ์ ์ด๋ค. ์ ๋์จ ํ์ธ๋์ ๊ดํธ๋ฅผ ์น ์ด์ ๋ ์๋ ์ค๋ช ํ๊ฒ ์ง๋ง ์ ๋์จ ํ์ธ๋๋ฅผ ์ ์ฐ๊ณ bfs๋ง์ผ๋ก ํ์ด ํ๋ ๋ฐฉ๋ฒ๋ ์๊ธฐ ๋๋ฌธ์ด๋ค. (์๋ ์ค๋ช ) 1. ์ ๋์จ ํ์ธ๋ ํ์ด ์ฃผ์ด์ง ๊ทธ๋ํ์์ dfs๋ฅผ ํตํด์ ์ฌ์ดํด์ ํ์ธํ๊ณ ํด๋น ์ฌ์ดํด์ ํ๋์ safezone ๊ทธ๋ฃน์ผ๋ก ๋ฌถ๋ ๊ณผ์ ์ ๋ฐ๋ณตํด์ผํ๋๋ฐ ์ด ๊ณผ์ ์์ ์ ๋์จ ํ.. 2022. 10. 2. [๋ฐฑ์ค] 2146 ๋ค๋ฆฌ ๋ง๋ค๊ธฐ (Python/ํ์ด์ฌ) https://www.acmicpc.net/problem/2146 2146๋ฒ: ๋ค๋ฆฌ ๋ง๋ค๊ธฐ ์ฌ๋ฌ ์ฌ์ผ๋ก ์ด๋ฃจ์ด์ง ๋๋ผ๊ฐ ์๋ค. ์ด ๋๋ผ์ ๋ํต๋ น์ ์ฌ์ ์๋ ๋ค๋ฆฌ๋ฅผ ๋ง๋ค๊ฒ ๋ค๋ ๊ณต์ฝ์ผ๋ก ์ธ๊ธฐ๋ชฐ์ด๋ฅผ ํด ๋น์ ๋ ์ ์์๋ค. ํ์ง๋ง ๋ง์ ๋ํต๋ น์ ์ทจ์ํ์, ๋ค๋ฆฌ๋ฅผ ๋๋๋ค๋ ๊ฒ์ด ์๊น๋ค www.acmicpc.net 1. ๊ธฐ๋ณธ ์ ๊ทผ์ ๊ฐ๊ฐ์ ์ฌ์ ๋ค๋ฅธ ๋ฒํธ๋ฅผ ๋ถ์ฌํ๊ณ ๊ฐ๊ฐ์ ์ฌ์ ๋ํด์ bfs๋ฅผ ํตํด์ ๋ค๋ฆฌ์ ์ต์ ๊ธธ์ด๋ฅผ ๊ตฌํ๋ ๊ฒ์ด๋ค. 2. ๋ค๋ง ๋ฉ๋ชจ๋ฆฌ์ด๊ณผ๊ฐ ๋๊ธฐ ์ฌ์์ visited๋ฐฐ์ด์ ์ ํ์ฉํด์ผ ํ๋ค. ๋ ๊ฐ์ ๊ฒฝ์ฐ๋ ๋ค๋ฆฌ ๊ฑด์คํ๋ bfs ํจ์ ์์ visited๋ฐฐ์ด์ ํ๋ ๋ง๋ค๊ณ , ์ฌ์ ๋ฒํธ์ ๋ํ visited๋ฐฐ์ด์ ํ๋ ๋ ๋ง๋ค์ด์ ํ ๋ฒ ํ์ํ ์ฌ์ ๋ํด์ ๋ค์ ํ์ํ์ง ์๋๋ก ํ๋ค. 3. ๋ค๋ฆฌ๋ฅผ .. 2022. 10. 1. [์๊ณ ๋ฆฌ์ฆ] ๋ค์ต์คํธ๋ผ (Dijkstra) ๋ค์ต์คํธ๋ผ (Dijkstra) ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ด๋ โ ์์ ๊ฐ์ค์น๊ฐ ์๋ ๊ทธ๋ํ์ ํ ์ ์ ์์ ๋ชจ๋ ์ ์ ๊น์ง์ ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐ๊ฐ ๊ตฌํ๋ ์๊ณ ๋ฆฌ์ฆ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์๋ฆฌ * P[a][b]: a์ b ์ฌ์ด์ ๊ฑฐ๋ฆฌ ์ถ๋ฐ์ ์ผ๋ก๋ถํฐ ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ์ ์ฅํ ๋ฐฐ์ด distance[v]์ ๋ง๋ค๊ณ ์ถ๋ฐ ๋ ธ๋๋ 0, ๋๋จธ์ง ๋ ธ๋๋ค์ ์ถฉ๋ถํ ํฐ ๊ฐ์ผ๋ก ์ด๊ธฐํ ํ๋ค. ํ์ฌ ๋ ธ๋ Current๋ฅผ ์ถ๋ฐ ๋ ธ๋์ ๋ฒํธ๋ก ์ค์ ํ๋ค. Current๋ก๋ถํฐ ๊ฐ ์ ์๋ ์์์ ๋ ธ๋ Next์ ๋ํด distance[Current] + P[Current][Next](A๋ฅผ ๊ฑฐ์ณ์ B๋ก ๊ฐ๋ ์ต๋จ๊ฑฐ๋ฆฌ)์ distance[Next](ํ์ฌ๊น์ง ์๋ ค์ง B์ ์ต๋จ ๊ฑฐ๋ฆฌ)์ ๊ฐ์ ๋น๊ตํด์ ์งง์ ๊ฐ(์งง์ ๊ฒฝ๋ก)๋ก ๊ฐฑ์ ํ๋ค. Current์ ๋ชจ๋ ์ด์๋ ธ๋ N.. 2022. 10. 1. ์ด์ 1 ยทยทยท 30 31 32 33 34 35 36 ๋ค์