[์๋ฐ/Java] ๋ฌธ๊ณผ์๋ ์ดํดํ๋ DFS ์๊ณ ๋ฆฌ์ฆ! - ์ ๋ฌธํธ
๋ฌธ๊ณผ ์ถ์ ์ ํ์ ๊ฐ๋ฐ์๊ฐ ์ทจ์ ํ๊ธฐ ์ํด ๊ณต๋ถํ ๋ฐฉ์ ๊ทธ๋๋ก ์ค๋ช ํ๋ ๊ธฐ์ด DFS ๊ฐ์์ ๋๋ค :) ์ง๋ฃจํ ์ด๋ก ๊ฐ์๋ ์ต์ํ์ผ๋ก ์ค์ด๊ณ , ์ง์ ๋ฌธ์ ๋ฅผ ํ์ด๋ณด๋ฉฐ ๋ฐฐ์ฐ๋ ๊ฐ์๋ฅผ ์ค๋นํ์ต๋๋ค! ์ด ๊ฐ์๋ฅผ ๋ค์ผ์๋ฉด ๋ฐฑ์ค ๊ธฐ์ค์ผ๋ก ์ค๋ฒ ๋ฑ๊ธ์ DFS ๋ฌธ์ ๋ค์ ํผ์ ํ ์ ์๊ฒ ๋ ๊ฒ๋๋ค.
์๊ฐ์ 461๋ช
๋์ด๋ ์ด๊ธ
์๊ฐ๊ธฐํ 12๊ฐ์

๋ค๋ฅธ ์๊ฐ์๋ค์ด ์์ฃผ ๋ฌผ์ด๋ณด๋ ์ง๋ฌธ์ด ๊ถ๊ธํ์ ๊ฐ์?
- ํด๊ฒฐ
dfs ๋ถ๋ฌธ์ ์ด๋ ๊ฒ ์์ฑํด๋ ๋๋์?
import java.util.*; import java.io.*; public class jelly { static int size; static int[][] map; static boolean[][] visited; /
java์ฝ๋ฉ-ํ ์คํธ์๊ณ ๋ฆฌ์ฆdfsdnrwls9115
ใป
6๋ฌ ์
1
60
1
- ํด๊ฒฐ
x๋ y๋ฅผ ๊ฑฐ๊พธ๋ก ์ฐ๋ ๊ฐ๋ ์ด ๋๋ฌด ํท๊ฐ๋ฆฝ๋๋ค...
์ผ๋ฐ์ ์ผ๋ก ์ํ ์ขํ๊ณ๋ก ์๊ฐํ๋ฉด (2,3) ์ด๋ผํ์๋ x์ถ์ด 2, y์ถ์ด 3์ด์ง๋ง ์ฐ๋ฆฌ๋ ๋งต์ด๋ 2์ฐจ์ ๋ฆฌ์คํธ๋ก ์๊ฐํ๊ฒ๋์๋<p
java์ฝ๋ฉ-ํ ์คํธ์๊ณ ๋ฆฌ์ฆdfsdnrwls9115
ใป
6๋ฌ ์
1
74
2
- ํด๊ฒฐ
dfs ํ๋ผ๋ฏธํฐ์ count๋ฅผ ๋ฃ๋์ด์
์๋ ํ์ธ์. ๊ธฐ์กด์ฒ๋ผ dfsํจ์๋ด์์ ํจ์๊ฐ ์คํ๋ ๋๋ง๋ค answer++๋ฅผ ํด์ ์กฐ๊ฑด์ ์ผ์น ํ ๋ ๊ทธ๋ฅ answer๋ฅผ ์ถ๋ ฅํ๊ฒํด๋ ๋ ๊ฒ๊ฐ์๋ฐcount๋ผ๋ ํ๋ผ๋ฏธ
java์ฝ๋ฉ-ํ ์คํธ์๊ณ ๋ฆฌ์ฆdfsdnrwls9115
ใป
6๋ฌ ์
1
54
2
- ํด๊ฒฐ
graph ์ฑ์ธ๋ for๋ฌธ ์ค๊ณ ์ง๋ฌธ
๊ทธ ์ ๋ฌธ์ ๋ค๊น์ง๋ graph๋ฅผ ์ฑ์ธ ๋์กฐ๊ฑด๋ฌธ์์ i < M์ผ๋ก ๊ฐ์ ์ ๊ฐ์๋ก ํ๋๋ฐ ์ ์ด๋ฒ๋ฌธ์ ์์๋ i <=N์ผ๋ก ํ๋์? ์ ์ 2์ฐจ์ ๋ฐฐ์ด์ ๊ฐ๋
java์ฝ๋ฉ-ํ ์คํธ์๊ณ ๋ฆฌ์ฆdfsdnrwls9115
ใป
6๋ฌ ์
1
58
2
- ํด๊ฒฐ
์ง๋ฌธ์์ต๋๋ค.
ํน์ ์ด๋ฐ ์ ํ์์ N ์ด ํฌ๋ฉด ArrayList ๋ฅผ ์ฌ์ฉํด์ผํ๋๋ฐ 2์ฐจ์ ๋ฐฐ์ด ์ด๋ ์ด ๋ฆฌ์คํธ ์ฌ์ฉ์ ์ด๋ค์์ผ๋ก ํ๋์??
java์ฝ๋ฉ-ํ ์คํธ์๊ณ ๋ฆฌ์ฆdfseovnfjfpa
ใป
9๋ฌ ์
1
64
1
- ํด๊ฒฐ
๋ค๋ฅธ ๊ฐ์ ์ธ์ ๋์ค๋์ฉ?
์๋ ํ์ธ์! 24๋ ๋๋ถํฐ ๊ฐ์ ์ ๋ณด๊ณ ์์ต๋๋ค!๋๋ถ์ ์๊ณ ๋ฆฌ์ฆ์ด ์ฌ๋ฏธ์์ด์ก์ต๋๋ค!์ด์ง์ค๋น๋ฅผ ์ํด ๊ฐ์๋ฅผ
java์ฝ๋ฉ-ํ ์คํธ์๊ณ ๋ฆฌ์ฆdfs์ธ์ง:)
ใป
9๋ฌ ์
1
84
2
- ํด๊ฒฐ
๋ ธ๋๊ฐ ๊ฑฐ๋ฆฌ ๊ณ์ฐ
๊ฐ์ ์์๋ง๋ค ์ง๋ฌธ์ด ์์ผ๋ฉด ์ธ์ ๋ ๊ทธ๋ฆฌ๊ณ ๋ฐ๋ก ์ง๋ฌธ ๋จ๊ฒจ์ฃผ์ธ์! ์ง๋ฌธํ ๋ ๊ฐ์ฅ ์ ํํ๊ฒ ์ดํดํ ์ ์์ต๋๋ค.ํด๋น ์์๊ณผ ๊ด๋ จ๋ ์ง๋ฌธ๋ค์ ํด์ฃผ์ค ๋ ์ ๊ฐ ๊ฐ์ฅ ์ ํํ ๋ต๋ณ ๋๋ฆด
java์ฝ๋ฉ-ํ ์คํธ์๊ณ ๋ฆฌ์ฆdfsnurugji
ใป
1
132
1
- ํด๊ฒฐ
์๋ ํ์ธ์, ํน์ ๋ค๋ฅธ๋ฌธ์ ๋ ์ฌ์ญค๋ณผ ์ ์์๊น์?
import java.util.*; public class Main { static int N; static ArrayList[] graph; static Ar
java์ฝ๋ฉ-ํ ์คํธ์๊ณ ๋ฆฌ์ฆdfs๊น์ํ
ใป
1
124
1
- ํด๊ฒฐ
์ต๊ทผ์ ์ฌ๋ฆฐ ์ง๋ฌธ, ์ฝ๋๋ธ๋ญ์ผ๋ก ๊ณต์ ๋๋ฆฝ๋๋ค!
import java.util.*; public class Main { static int N, M, R; static int[] answer; static ArrayList<Int
java์ฝ๋ฉ-ํ ์คํธ์๊ณ ๋ฆฌ์ฆdfs๊น์ํ
ใป
1
128
1
- ํด๊ฒฐ
์ง๋ฌธ์ด ์์ต๋๋ค. dfs ๋ฉ์๋์ order๋ฅผ ์ด๋ ๊ฒ ๊ตฌํํ๋ฉด ์๋๋ ์ด์ ๊ฐ ๋ฌด์์ธ๊ฐ์?
<img src="https://cdn.inflearn.com/public/files/posts/406d340d-2a3c-4599-a662-700991e7e909/25e333fa-601c-4cdc-b0c5-f094b920532f.png" media-type="img"
java์ฝ๋ฉ-ํ ์คํธ์๊ณ ๋ฆฌ์ฆdfs๊น์ํ
ใป
0
121
2
- ํด๊ฒฐ
๊น์ด์ฐ์ ํ์2 ๋ฐฑ์ค 24480 ์์ ๋ ธํธ์...
//2. ์ค๋ฆ์ฐจ์ ์ ๋ ฌ -> ๋ด๋ฆผ์ฐจ์ ์ ๋ ฌ๋ก ์์ ํ์ ์ผ ํ ๋ฏ ^^
java์ฝ๋ฉ-ํ ์คํธ์๊ณ ๋ฆฌ์ฆdfsEdwards
ใป
1
108
1
- ํด๊ฒฐ
Max๋ก ์ด๊ธฐํํ๋ ์ด์
๋ฐฐ์ด๋ค์ ์ ๋ ฅ๋ฐ์ n+1, m+1์ด ์๋ max๋ก ์ด๊ธฐํํ๋ ์ด์ ๋ฅผ ์ ๋ชจ๋ฅด๊ฒ ์ต๋๋ค ๊ฐ์ ์์๋ง๋ค ์ง๋ฌธ์ด ์์ผ๋ฉด ์ธ์ ๋ ๊ทธ๋ฆฌ๊ณ ๋ฐ๋ก ์ง๋ฌธ ๋จ๊ฒจ์ฃผ์ธ์! ์ง๋ฌธํ ๋ ๊ฐ์ฅ ์ ํํ
color.park
ใป
1
175
2
- ํด๊ฒฐ
๋ฐฑ์ค 24479 ๋ฌธ์ ์ ์ถ ๊ฒฐ๊ณผ "ํ๋ ธ์ต๋๋ค" ๋ผ๊ณ ๋ง ๋์์ ์ด๋ค ๋ถ๋ถ์ด ํ๋ ธ๋์ง ์ ๋ชจ๋ฅด๊ฒ ์ด์ ํผ๋๋ฐฑ ๋ถํ๋๋ฆฝ๋๋ค
package com.study.book.graph; import java.util.*; import java.io.*; public class Baekjoon24479 { private stati
java์ฝ๋ฉ-ํ ์คํธ์๊ณ ๋ฆฌ์ฆdfs์ด์ฌ๋ฏผ
ใป
1
229
3
- ํด๊ฒฐ
graph ๋ง๋ค๋ boolean[][] ์ผ๋ก ๋ง๋๋ ๊ฒฝ์ฐ๋ int[][] ๋ ArrayList<Integer>[] ๋ก ๋ง๋๋ ๊ธฐ์ค์ด ์ด๋ป๊ฒ ๋๋์?
๊ฐ์ ์์๋ง๋ค ์ง๋ฌธ์ด ์์ผ๋ฉด ์ธ์ ๋ ๊ทธ๋ฆฌ๊ณ ๋ฐ๋ก ์ง๋ฌธ ๋จ๊ฒจ์ฃผ์ธ์! ์ง๋ฌธํ ๋ ๊ฐ์ฅ ์ ํํ๊ฒ ์ดํดํ ์ ์์ต๋๋ค.ํด๋น ์์๊ณผ ๊ด๋ จ๋ ์ง๋ฌธ๋ค์ ํด์ฃผ์ค ๋ ์ ๊ฐ ๊ฐ์ฅ ์ ํํ ๋ต๋ณ ๋๋ฆด
java์ฝ๋ฉ-ํ ์คํธ์๊ณ ๋ฆฌ์ฆdfsewgregerg c
ใป
1
195
2
- ํด๊ฒฐ
graph๋ฅผ 2์ฐจ์ ๋ฐฐ์ด ๋๋ List๋ก ํ๋ ๊ธฐ์ค์ ์ด๋ค์์ผ๋ก ์ก์ผ๋ฉด ์ข์๊น์...?
์์ง 2์ฐจ์ ๋ฐฐ์ด ๋๋ List๋ก ํด์ผ๋๋๊ฒ์ ์ ํํ๋ ๊ธฐ์ค์ด ์ ์์กํ๋๋ฐ ๋ฌธ์ ์์ ์ํ๋ ์ถ๋ ฅ ํํ๊ฐ ์ฐ๊ฒฐ๋ ๋ชจ๋ ๊ฒ๋ค์ ์ถ๋ ฅํ๋ ๋๋์ผ๋ก ์ง๋ฌธํ๋ค๋ฉด List ์ด๊ณ , ๊ทธ์ธ์๋ 2์ฐจ์ ๋ฐฐ์ด๋ก ํ๋ฉด ๋ ๊น์...? ใ ใ
java์ฝ๋ฉ-ํ ์คํธ์๊ณ ๋ฆฌ์ฆdfsyhd4286
ใป
1
215
1
- ํด๊ฒฐ
๊ฐ์ฌ๋ ์๋ ํ์ธ์! ๊น์ด ์ฐ์ ํ์ 2 (๋ฐฑ์ค 24480)์์ ์ ๊ณตํ๋ ํ์ด ์ฝ๋์์ ๊ถ๊ธํ ์ ์ด ์์ด์ ์ง๋ฌธ ๋๋ฆฝ๋๋ค!
import java.util.*; import java.io.*; class Main { final static int MAX = 100000 + 10; static ArrayList<Integer>
java์ฝ๋ฉ-ํ ์คํธ์๊ณ ๋ฆฌ์ฆdfs๋ฌด์๋นํ ๋ญ๋ง์ฃผ๋จน
ใป
1
314
3
- ํด๊ฒฐ
์ด์ ๊ณ์ฐ
count๋ผ๋ ๋งค๊ฐ๋ณ์๋ฅผ ๊ฐ์ด ์ ๋ฌํด์ฃผ๊ธฐ ๋ณด๋ค dfs๊ฐ ํธ์ถ๋ ๋๋ง๋ค answer๋ฅผ ๋ฃ์ด์ฃผ๋ ๋ฐฉ์์ผ๋ก ํ์ด๋ดค๋๋ฐ ์์ธ์ง end ๊ฐ์ ์ฐพ์์ ๋ return์ด ์ ์ฉ์ด ์๋๋ ๊ฑฐ ๊ฐ์ต๋๋ค. ํน์ ์ด๋ค ๋ฌธ์ ๊ฐ ์๋์ง ๋ด์ฃผ์ค ์ ์๋์? <p
java์ฝ๋ฉ-ํ ์คํธ์๊ณ ๋ฆฌ์ฆdfs๊นํ์ค
ใป
1
347
3
- ํด๊ฒฐ
์ฐ๊ฒฐ ์์์ ๊ฐ์ (๋ฐฑ์ค 11724)
๊ฐ์ ์์๋ง๋ค ์ง๋ฌธ์ด ์์ผ๋ฉด ์ธ์ ๋ ๊ทธ๋ฆฌ๊ณ ๋ฐ๋ก ์ง๋ฌธ ๋จ๊ฒจ์ฃผ์ธ์! ์ง๋ฌธํ ๋ ๊ฐ์ฅ ์ ํํ๊ฒ ์ดํดํ ์ ์์ต๋๋ค.ํด๋น ์์๊ณผ ๊ด๋ จ๋ ์ง๋ฌธ๋ค์ ํด์ฃผ์ค ๋ ์ ๊ฐ ๊ฐ์ฅ ์ ํํ ๋ต๋ณ ๋๋ฆด
java์ฝ๋ฉ-ํ ์คํธ์๊ณ ๋ฆฌ์ฆdfs๊นํ์ค
ใป
1
255
1
- ํด๊ฒฐ
๋ฐฑ์ค 24479 ๋ฌธ์ ์๊ฐ ์ด๊ณผ ์ง๋ฌธ ๋๋ ค์
์๋ ํ์ธ์ ๋ฐฑ์ค์์ ํ ์คํธ ๊ฒฐ๊ณผ ์๊ฐ ์ด๊ณผ ์ค๋ฅ๊ฐ ๋ฉ๋๋ค . ํ์ธ ํ๋ฒ ๊ฐ๋ฅํ ๊น์?import java.io.*; import java.util.*; public class Main
java์ฝ๋ฉ-ํ ์คํธ์๊ณ ๋ฆฌ์ฆdfs์์ฑ์ ์์
ใป
1
369
1
- ํด๊ฒฐ
๋ฐฑ์ค ์คํ์ ํ๋ฆฝ๋๋ค.
์๋ ํ์ธ์ ๊ฐ์ฌ๋. ๋ฌธ์ ๋ฅผ ํ๊ณ ๋ฐฑ์ค์ ์ ์ถํ์ ๋ ๊ณ์ ์ค๋ต์ผ๋ก ๋์ ์ง๋ฌธ ๋๋ฆฝ๋๋ค..์ ๊ฐ ๋ดค์ ๋ ๊ฐ์ฌ๋ ์ฝ๋๋ ๊ฑฐ์ ๋น์ทํ๊ฒ ์์ ๊น์ง ํ ๊ฒ ๊ฐ์๋ฐ.. ์ด๋ค ๋ถ๋ถ์ด ์๋ชป๋์๋์ง ํ์ธ ํ๋ฒ ๋ถํ๋๋ฆฝ๋๋ค.impor
java์ฝ๋ฉ-ํ ์คํธ์๊ณ ๋ฆฌ์ฆdfsendeavor
ใป
1
360
1






