πκΉμ΄ μ°μ νμ :
λ―Έλ‘λ₯Ό νμν λ ν λ°©ν₯μΌλ‘ κ° μ μμ λκΉμ§ κ³μ κ°λ€κ° λ μ΄μ κ° μ μκ² λλ©΄ λ€μ κ°μ₯ κ°κΉμ΄ κ°λ¦ΌκΈΈλ‘ λμμμ μ΄κ³³μΌλ‘λΆν° λ€λ₯Έ λ°©ν₯μΌλ‘ λ€μ νμμ μ§ννλ λ°©λ²κ³Ό μ μ¬νλ€.
μ¦, λκ²(wide) νμνκΈ° μ μ κΉκ²(deep) νμνλ κ²μ΄λ€.
https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html
[μκ³ λ¦¬μ¦] κΉμ΄ μ°μ νμ(DFS)μ΄λ - Heee's Development Blog
Step by step goes a long way.
gmlwjd9405.github.io
κΉμ΄ μ°μ νμ(DFS)μ΄ λλΉ μ°μ νμ(BFS)λ³΄λ€ μ’ λ κ°λ¨νλ€.
λ¨μ κ²μ μλ μ체λ λλΉ μ°μ νμ(BFS)μ λΉν΄μ λ리λ€.
μ΅λ¨κ²½λ‘λ₯Ό μ°Ύμλ©΄ BFSλ₯Ό μ΄μ©ν΄μΌ νλ€.
DFSλ μ΅λ¨ κ²½λ‘κ° λλ€λ 보μ₯λ μμ λΏλλ¬ κ²½λ‘κ° λ€μλΌλ©΄, ν΄μ λ€λ€λ₯΄λ©΄ νμμ΄ μ’ λ£λλ―λ‘ μ΅μ ν΄κ° μλ μλ μλ€.
BFSμ λ§μ°¬κ°μ§λ‘ λ―Έλ‘νμμ ν΄λΉν¨.
νκ²μ B
λλ¦° λ‘μ§μ μ€κ° κ²½λ‘λ₯Ό νμΈ νλ©΄ λ€μκ³Ό κ°λ€.
ꡬν : DFS + μ¬κ· :
static int dx2[] = {1, -1, 0, 0};
static int dy2[] = {0, 0, 1, -1};
static String arr2[][];
static void dfsRecursion(String[][] arr, boolean[][] visited, int x, int y) {
// μ’
λ£μ‘°κ±΄μ΄ μλ€λ©΄ 무ν루νμ λΉ μ§ μλ μλ€.
// μ ν©ν μ’
λ£μ‘°κ±΄μ λͺ
μν΄μ€μ΄ μ’λ€. κ°λ Ή λ―Έλ‘μ λν ν΄λ΅μ΄ μμ μλ μμΌλκΉ.
// μ°Ύμκ°λ κ²½λ‘ νμΈμ©.
/* for (int i = 0 ; i < lineNums2; i ++ ) {
for (int j = 0 ; j < charNums2; j ++ ) {
if (visited[j][i]) {
arr2[j][i] = "*";
}
System.out.print(arr2[j][i]);
}
System.out.println("");
}
*/
// λͺ©μ μ§λ Bκ° λκΈ° λλ¬Έμ.
if (arr[x][y].equals("B")) {
System.out.println("B found...");
cnt2++;
return;
}
// λ°©λ¬Έν κ²½λ‘μ λν νμλ₯Ό νλ€.
visited[x][y] = true;
for (int i=0;i<4;i++) {
int nx = x + dx2[i];
int ny = y + dy2[i];
if (nx >=0 && ny >=0 && nx < charNums2 && ny < lineNums2) {
if ((!visited[nx][ny] && arr[nx][ny].equals(" ") ) || arr[nx][ny].equals("B")) {
dfsRecursion(arr,visited,nx,ny);
visited[nx][ny] = false;
}
}
}
'ALGORITHM' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[LIS] λ°±μ€ 2631 μ€ μΈμ°κΈ° (0) | 2022.08.28 |
---|---|
[LIS] λ°±μ€ 11053 κ°μ₯ κΈ΄ μ¦κ°νλ λΆλΆ μμ΄ (0) | 2022.08.28 |
JAVA λ―Έλ‘νμ / BFS (0) | 2022.06.14 |
λ°±μ€ 2837 / java (0) | 2022.04.05 |
SHA-256 (Secure Hash Algorithm) (0) | 2022.04.04 |