์๊ณ ๋ฆฌ์ฆ/BOJ
โจ ๋ค์ต์คํธ๋ผ โ ์ต๋จ๊ฒฝ๋ก https://www.acmicpc.net/problem/1504 1504๋ฒ: ํน์ ํ ์ต๋จ ๊ฒฝ๋ก ์ฒซ์งธ ์ค์ ์ ์ ์ ๊ฐ์ N๊ณผ ๊ฐ์ ์ ๊ฐ์ E๊ฐ ์ฃผ์ด์ง๋ค. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) ๋์งธ ์ค๋ถํฐ E๊ฐ์ ์ค์ ๊ฑธ์ณ์ ์ธ ๊ฐ์ ์ ์ a, b, c๊ฐ ์ฃผ์ด์ง๋๋ฐ, a๋ฒ ์ ์ ์์ b๋ฒ ์ ์ ๊น์ง ์๋ฐฉํฅ ๊ธธ์ด ์กด www.acmicpc.net ๐ ๊ณ ๋ คํด์ผํ ์ ๋ฐฉํฅ์ด ์๋ ๊ทธ๋ํ์ด๋ค. 1๋ฒ ์ ์ ์์ N๋ฒ ์ ์ ์ผ๋ก ์ต๋จ๊ฑฐ๋ฆฌ๋ก ์ด๋ํ๋ค. ์ฃผ์ด์ง ๋ ์ ์ ์ ๋ฐ๋์ ๊ฑฐ์ณ์ผ ํ๋ค. ๋ ์ ์ ์ด v1, v2๋ผ๋ฉด 1 โ v1 โ v2 โ N ๋๋ 1 โ v2 โ v1 โ N ๋๊ฐ์ง ๋ฐฉ๋ฒ์ผ๋ก ์ด๋ํ ์ ์๋ค. ๐น๏ธ ํ์ด ๋ฐฉ๋ฒ 1๏ธโฃ ๋
ธ๋์ ๋ํ ์ ๋ณด (์ด๋ํด์ผํ๋ ๋
ธ๋ = v, ํด..
์๊ณ ๋ฆฌ์ฆ/BOJ
โจ ๊ทธ๋ํ ํ์ โจ BFS, ๋ค์ต์คํธ๋ผ โ ์ต๋จ ๊ฒฝ๋ก ์ฐพ๊ธฐ https://www.acmicpc.net/problem/18352 18352๋ฒ: ํน์ ๊ฑฐ๋ฆฌ์ ๋์ ์ฐพ๊ธฐ ์ฒซ์งธ ์ค์ ๋์์ ๊ฐ์ N, ๋๋ก์ ๊ฐ์ M, ๊ฑฐ๋ฆฌ ์ ๋ณด K, ์ถ๋ฐ ๋์์ ๋ฒํธ X๊ฐ ์ฃผ์ด์ง๋ค. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) ๋์งธ ์ค๋ถํฐ M๊ฐ์ ์ค์ ๊ฑธ์ณ์ ๋ ๊ฐ www.acmicpc.net ๐ ๊ณ ๋ คํด์ผํ ์ ์ถ๋ฐ ๋์์ ๋ํ ์ ๋ณด๊ฐ ์กด์ฌํ๋ค. ์ต๋จ ๊ฑฐ๋ฆฌ์ ๋ํ ์ ๋ณด๊ฐ ์กด์ฌํ๋ค. โ ํด๋นํ๋ ์ต๋จ ๊ฑฐ๋ฆฌ์ธ ๋์๋ฅผ ์ฐพ์ผ๋ฉด ๋๋ค. ํ๋์ ๋์์์ ๋ค๋ฅธ ๋ชจ๋ ๋์๊น์ง์ ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํด์ผํ๊ธฐ ๋๋ฌธ์ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ๋ค. ๋์๊ฐ์ ๊ฑฐ๋ฆฌ๊ฐ ๋ชจ๋ 1์ด๊ธฐ ๋๋ฌธ..
์๊ณ ๋ฆฌ์ฆ/BOJ
โจ ์ต๋จ๊ฒฝ๋ก ์๊ณ ๋ฆฌ์ฆ โก๏ธ ๋ฒจ๋ง ํฌ๋ ์๊ณ ๋ฆฌ์ฆ https://www.acmicpc.net/problem/11657 11657๋ฒ: ํ์๋จธ์ ์ฒซ์งธ ์ค์ ๋์์ ๊ฐ์ N (1 ≤ N ≤ 500), ๋ฒ์ค ๋
ธ์ ์ ๊ฐ์ M (1 ≤ M ≤ 6,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ M๊ฐ์ ์ค์๋ ๋ฒ์ค ๋
ธ์ ์ ์ ๋ณด A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)๊ฐ ์ฃผ์ด์ง๋ค. www.acmicpc.net ๐ ๊ณ ๋ คํด์ผํ ์ C < 0 ์ธ ๊ฒฝ์ฐ ํ์๋จธ์ ์ผ๋ก ์๊ฐ์ ๋๋์๊ฐ๋ ๊ฒฝ์ฐ์ด๋ค. โ ์์ ๊ฐ์ค์น ์กด์ฌ 1๋ฒ ๋์์์ ์ถ๋ฐํ๋ค. ์์ ์ฌ์ดํด์ด ์๊ฑฐ๋ ๊ฒฝ๋ก๊ฐ ์์ ์๋ค๋ฉด -1 ์ถ๋ ฅ ์ค๋ฒํ๋ก์ฐ ๋ฒ์ ์กฐ์ฌ ๐น๏ธ ํ์ด๊ณผ์ 1๏ธโฃ ๊ฐ์ ๊ณผ ์ ์ , ๋น์ฉ์ ์ ๋ณด๋ฅผ ์ ์ฅํ๋ค. 2๏ธโฃ ๋ฒจ๋ง ํฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉ..
์๊ณ ๋ฆฌ์ฆ/BOJ
โจ ์ต๋จ๊ฒฝ๋ก ์๊ณ ๋ฆฌ์ฆ โก๏ธ ๋ฒจ๋ง ํฌ๋ ์๊ณ ๋ฆฌ์ฆ https://www.acmicpc.net/problem/1865 1865๋ฒ: ์ํ ์ฒซ ๋ฒ์งธ ์ค์๋ ํ
์คํธ์ผ์ด์ค์ ๊ฐ์ TC(1 ≤ TC ≤ 5)๊ฐ ์ฃผ์ด์ง๋ค. ๊ทธ๋ฆฌ๊ณ ๋ ๋ฒ์งธ ์ค๋ถํฐ TC๊ฐ์ ํ
์คํธ์ผ์ด์ค๊ฐ ์ฐจ๋ก๋ก ์ฃผ์ด์ง๋๋ฐ ๊ฐ ํ
์คํธ์ผ์ด์ค์ ์ฒซ ๋ฒ์งธ ์ค์๋ ์ง์ ์ ์ N(1 ≤ N ≤ 500), www.acmicpc.net ๐ ๊ณ ๋ คํด์ผํ ์ ํ ์ง์ ์์ ์ถ๋ฐํ์ฌ ๋ค์ ์ถ๋ฐํ๋ ์ง์ ์ผ๋ก ๋์์์ ๋ ์ฒ์ ์ถ๋ฐํ์ ๋๋ณด๋ค ์๊ฐ์ด ๋๋์๊ฐ ์๋ ๊ฒฝ์ฐ ํ๋จ โ ์ํ ๋ด์์ ์๊ฐ์ด ๊ฑฐ๊พธ๋ก ํ๋ฌ๊ฐ๋ค. โก๏ธ ์์ ๊ฐ์ค์น ์กด์ฌ & ์์ ์ฌ์ดํด ์กด์ฌ O ํ ์ง์ ์์ ์ถ๋ฐํ๋ค. (ํน์ ์ง์ ์์ ์ถ๋ฐ X) ์์์ ์ ์ ์์ ์ถ๋ฐ ๋ชจ๋ ์ ์ ์์ ์ถ๋ฐ ๋ ์ง์ ์ ์ฐ๊ฒฐํ๋ ๋๋ก๊ฐ ํ ..
์๊ณ ๋ฆฌ์ฆ/๐๏ธ ์ ๋ฆฌ
DP(๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ)๋ฅผ ํ์ฉํ ๋ํ์ ์ธ ์ต๋จ ๊ฒฝ๋ก ํ์ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ํ๋์ ์ ์ ์์ ๋ค๋ฅธ ๋ชจ๋ ์ ์ ๊น์ง์ ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์์ ์ฌ์ฉ๋๋ค. ์ต๋จ ๊ฑฐ๋ฆฌ๋ ์ฌ๋ฌ ๊ฐ์ง ์ต๋จ ๊ฑฐ๋ฆฌ๋ก ์ด๋ฃจ์ด์ ธ ์๊ธฐ ๋๋ฌธ์ ์์ ๋ฌธ์ ๊ฐ ํฐ ๋ฌธ์ ์ ๋ถ๋ถ ์งํฉ์ ์ํด์๋ค๊ณ ๋ณผ ์ ์๋ค. ํ๋์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ ๋ ๊ทธ ์ด์ ๊น์ง ๊ตฌํ๋ ์ต๋จ ๊ฑฐ๋ฆฌ ์ ๋ณด๋ฅผ ๊ทธ๋๋ก ์ฌ์ฉํ๋ ํน์ง์ด ์๋ค. ๐น๏ธ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ ๊ณผ์ ์ถ๋ฐ ๋
ธ๋ ์ค์ ์ถ๋ฐ ๋
ธ๋๋ฅผ ๊ธฐ์ค์ผ๋ก ๊ฐ ๋
ธ๋์ ์ต์ ๋น์ฉ ์ ์ฅ ๋ฐฉ๋ฌธํ์ง ์์ ๋
ธ๋ ์ค์์ ๊ฐ์ฅ ๋น์ฉ์ด ์ ์ ๋
ธ๋ ์ ํ ํด๋น ๋
ธ๋ ๊ฑฐ์ณ์ ํน์ ํ ๋
ธ๋๋ก ๊ฐ๋ ๊ฒฝ์ฐ ๊ณ ๋ คํ์ฌ ์ต์ ๋น์ฉ ๊ฐฑ์ 3๏ธโฃ, 4๏ธโฃ๋ฒ ๋ฐ๋ณต ๊ธฐ๋ณธ์ ์ธ ๋ค์ต์คํธ๋ผ - ์ ํํ์ public class Main{ static int INF = 10000..