๋ฌธ์ https://www.acmicpc.net/problem/5427 5427๋ฒ: ๋ถ ์๊ทผ์ด๋ ๋น ๊ณต๊ฐ๊ณผ ๋ฒฝ์ผ๋ก ์ด๋ฃจ์ด์ง ๊ฑด๋ฌผ์ ๊ฐํ์๋ค. ๊ฑด๋ฌผ์ ์ผ๋ถ์๋ ๋ถ์ด ๋ฌ๊ณ , ์๊ทผ์ด๋ ์ถ๊ตฌ๋ฅผ ํฅํด ๋ฐ๊ณ ์๋ค. ๋งค ์ด๋ง๋ค, ๋ถ์ ๋์๋จ๋ถ ๋ฐฉํฅ์ผ๋ก ์ธ์ ํ ๋น ๊ณต๊ฐ์ผ๋ก ํผ์ ธ๋๊ฐ๋ค. ๋ฒฝ์ www.acmicpc.net ํ์ด ์ ํ์ ์ธ BFS ์๋ฎฌ๋ ์ด์
๋ฌธ์ ! ๋ชจ๋ ๋ก์ง์ ์์์ ๋ถ์ด ๋ฒ์ง๋ ๊ณผ์ ๋ง ๊ผผ๊ผผํ ์์ฑํด์ฃผ๋ฉด ๋๋ค. BFS ๋ก์ง ์์ 1. Depth๊ฐ ๋์ด๋ ๋ ๋ง๋ค ๋ถ ํ์ฐ 2. ๊ฐ๋ ค๋ ๊ธธ์ ๋ถ์ด ์์ผ๋ฉด Continue 3. ์ข
๋ฃ ์กฐ๊ฑด ํ์ธ 4. ์๊ทผ์ด ์ด๋ ๊ฐ๋ฅ ๊ฒฝ๋ก ํ์ ๋ถ์ด ๋ฒ์ง๋ ๊ณผ์ 1. ๋ถ์ด ์๋ก ๋ฒ์ง ๊ณณ์ ์ ์ฅํ ๋ฆฌ์คํธ ์ ์ธ 2. ํ์ฌ ๋ถ ๋ฆฌ์คํธ๋ฅผ ๋๋ฉฐ ์๋ก ๋ฒ์ง ๋ฆฌ์คํธ์ ์ถ๊ฐ 3. ํ์ฌ ๋ถ ๋ฆฌ์คํธ๋ฅผ..
๋ฌธ์ ํ์ด ๋จ์ํ win-lose ๊ฐ์์ ๋ฌด์น๋ถ ๊ฐ์๋ง ๋ง์ถ๋ฉด ๋๋ค๊ณ ์๊ฐํ๋ค๋ฉด ๋ฐ๋ก ์คํจ 1. ๊ฐ๋ฅํ ๋งค์น๋ค์ ๋ชจ๋ ์ดํด ๋ณด์์ผ ํจ: A - B,C,D,E,F / B-C,D,E,F / C-D,E,F / D-E,F / E-F 2. ๋งค์น๋ฅผ ๋๋ฉฐ ์น-ํจ / ๋ฌด-๋ฌด / ํจ-์น ์ ๊ฒฝ์ฐ๋ฅผ ์ดํด๋ด 3. ์ฌ๊ท๊ฐ 15ํ(์ด ๊ฒฝ๊ธฐ ํ์)๋ ๊ฒฝ์ฐ: ์ ํจํ ๊ฒฝ๊ธฐ ๊ฒฐ๊ณผ! ์ฝ๋ ๋๋ณด๊ธฐ import java.util.*; import java.io.*; public class Main { static final int T = 4; // ํ
์คํธ ์ผ์ด์ค ์ static int[][] game; static int[][] match = new int[15][2]; // A-BCDEF / B-CDEF ... ์ ์ฅ static bool..
๋ฌธ์ Silver3 ํ์ด ๊ทธ๋ํ ํ์(DFS)๋ฅผ ํตํด ์ธ์ ์ ์ ์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ . ์ธ์ ํ๋ ฌ์ booleanํ์ผ๋ก ์ ์ธํด ํ์ํ๋ ์ธ๋ฑ์ค์ ๊ฐ์ด true์ด๊ณ visited๋ฐฐ์ด์ด false๋ผ๋ฉด ํ์ํ๋ฉฐ, ๊ฒฐ๊ณผ๊ฐ cnt ์ฆ๊ฐ. ์ฝ๋ ๋๋ณด๊ธฐ import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ static boolean[][] arr; static boolean[] visited; static int N, cnt; public static void main(String[] args) throws Exception{ BufferedReader br = ..
๋ฌธ์ Gold5 https://www.acmicpc.net/problem/1753 1753๋ฒ: ์ต๋จ๊ฒฝ๋ก ์ฒซ์งธ ์ค์ ์ ์ ์ ๊ฐ์ V์ ๊ฐ์ ์ ๊ฐ์ E๊ฐ ์ฃผ์ด์ง๋ค. (1≤V≤20,000, 1≤E≤300,000) ๋ชจ๋ ์ ์ ์๋ 1๋ถํฐ V๊น์ง ๋ฒํธ๊ฐ ๋งค๊ฒจ์ ธ ์๋ค๊ณ ๊ฐ์ ํ๋ค. ๋์งธ ์ค์๋ ์์ ์ ์ ์ ๋ฒํธ K(1≤K≤V)๊ฐ ์ฃผ์ด์ง๋ค. www.acmicpc.net ํ์ด ์์์ ์์ ๋ชจ๋ ์ ์ ๊น์ง์ ์ต๋จ๊ฒฝ๋ก๋ฅผ ๊ตฌํ๋ ๋ค์ต์คํธ๋ผ(Dijkstra) ์๊ณ ๋ฆฌ์ฆ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ ๊ตฌํ - ์์์ ์์๋ถํฐ ๋ฐฉ๋ฌธ์ฌ๋ถ์ ์์์ ๋ถํฐ์ ์ต์ ๊ฒฝ๋ก ์ ์ ์ ํ์ - ์ต์ ๊ฒฝ๋ก ์ ์ ํ์ ํ, ํด๋น ์ ์ ์ ๋ํ distance๋ฐฐ์ด(ํด๋น ์ ์ ์ ๊ฒฝ์ ํด์ ๊ฐ ์ ์๋ ์ต๋จ ๊ฑฐ๋ฆฌ)์ ์ฌ์ค์ ๊ทธ๋ํ ์ ๋ณด๋ฅผ ์ฒ์ ์ธ์ ํ๋ ฌ๋ก ํ์์ผ๋ ํ
์ผ์ ํฌ๊ธฐ๊ฐ ๋งค..