주의! 이글은 개인 공부 목적으로 작성된 포스팅입니다.
잘못된 내용이 있을 수 있음을 주의해주세요.
✈️ 여정
진짜 5일 동안 DFS를 이해하기 위해 예제 문제도 풀어보고 "노드 탐색하는 코드를 안 보고 칠 수 있을 정도로 연습해야지!" 하는 생각으로 공부했다. 처음에는 하루 지나면 까먹고, 문제 풀어도 틀리고 했지만 포기하지 않고 계속 공부했다.
결론부터 말하면 나름 해당 과정이 DFS 이해해 도움이 됐고, 지금은 간단한 문제를 풀 수 있게 됐다.
👀 DFS?
DFS는 흔히 깊이 우선 탐색이라고 하며, 노드가 존재하면 해당 노드의 가장 밑바닥까지 탐색하는 것을 뜻한다.
Stack과 재귀함수로 구현할 수 있고 오늘은 재귀함수로 구현하는 예를 설명하며 DFS를 알아볼 것이다.
위 그림을 보자. 모든 노드가 연결되어있다.
만약, DFS 탐색을 한다면 탐색 순서가 어떻게 될까?
답 : 1->2->3->4->5
위와 같이 정답이 나온다. 자 그럼 왜 1 ~ 5까지 순서대로 방문이 됐는지 생각해보자.
DFS는 깊이 우선 탐색이다. 연결된 노드들을 먼저 탐색한다.
만약, [1, 2]를 먼저 입력했다면 DFS 알고리즘은 2번 노드를 먼저 탐색한다.
그럼 [1, 2]를 먼저 시작한 DFS 알고리즘은 그다음 노드인 [2, 3]을 탐색하고 [2, 4]를 진행하는 것이다.
⚙️ 코드로 구현해보자.
처음에는 방향성을 가지고 있는 그래프 탐색 알고리즘을 구현했었다.
하지만 백준에서 문제를 풀면서 무방향 그래프도 고려해야 한다는 점을 인지하고 다시 공부하느라 애를 먹었다..
fun main(args : Array<String>){
var command = readln().split(" ").map{ it.toInt() }
//4 5 1입력을 받는 코드
//4 : 정점의 개수 / 5: 간선의 개수 / 1 : 시작 인덱스
var map = Array<MutableList<Int>>(command[0] + 1){mutableListOf()}
var isCheck = Array(command[0] + 1){false}
/**
* 주의! 0을 사용하지 않으니 +1을 해서 초기화를 해야한다.
*
* 인접 리스트로 구현된 map 변수
* 방문 확인을 위한 isCheck 변수
*/
for(i in 0 until command[1]){
var line = readln().split(" ").map{ it.toInt() }
map[line[0]].add(line[1])
map[line[1]].add(line[0])
}
/**
* 간선의 수 만큼 입력을 받는다.
* 1 - 2 / 2 - 1 식으로 리스트에 등록해 무방향 그래프를 대응한다.
*/
for(i in map.indices){
map[i].sort()
}
/**
* why 정렬?
* 정렬을 하지 않을 경우 노드의 방문 순서가 올바르게 작동하지 않습니다.
* 고로 각 노드마다 정렬을 해줘야합니다.
*/
dfs(map,isCheck,command[2])
}
fun dfs(map: Array<MutableList<Int>>, isCheck: Array<Boolean>, startIndex : Int){
isCheck[startIndex] = true
println("$startIndex ")
for(i in map[startIndex]){
if(!isCheck[i]){
dfs(map,isCheck, i)
}
}
}입력
4 5 1
1 2
1 3
1 4
2 4
3 4
답 : 1 2 4 3
위 DFS는 인접리스트로 구현한 코드이다.
인접행렬도 사용할 수 있지만 행렬보단 인접리스트가 시간복잡도 면에서 유리하다.
🌈 연습 문제 - 백준 2667번
백준 2667번을 추천한다.
간단한 하게 DFS를 실습할 수 있는 문제이다.
나는 인접리스트를 사용해 DFS를 구현하고, 해당 문제를 해결했다.
어려웠던 점은 각 아파트 단지 안에 아파트가 몇 개 있는지 개수를 카운팅하는게 힘들었다.
풀이
fun main(args: Array<String>) {
var callCount = readln().toInt() // 몇번 입력 할 건지 입력받는 변수
var map = Array(callCount){mutableListOf<Int>()} // 아파트 정보를 저장할 인접리스트 생성
var isCheck = Array(callCount){mutableListOf(false)} // 아파트 방문 여부를 체크하는 변수
var list:ArrayList<Int> = arrayListOf() // 각 아파트의 개수를 저장할 변수
repeat(callCount){ //repeat을 사용해 입력 횟수만큼 반복
readln().forEachIndexed{i2,item ->
map[it].add(i2,item.toString().toInt()) //인접리스트에 아파트 정보 입력
isCheck[it].add(i2,false) // 해당하는 아파트 최초에 방문X 처리
}
}
for (i in map.indices){ // 아파트 세로 만큼
for (i2 in map[i].indices){ // 아파트 가로 만큼
var num = dfs(map,isCheck,i,i2) // dfs 탐색 후 return 받은 값을 저장하는 변수
if (num != 0){ // 사이즈 초과 또는 방문으로 인해 0이 리턴된 경우 제외
list.add(num) // 아닌 경우 list에 추가
}
}
}
println(list.size) // 탐색된 아파트 단지 개수 출력
list.sort() // 탐색된 아파트 단지안에 아파트 개수를 기준으로 오름차순 정렬
list.forEach {
println(it) // 아파트 개수 출력
}
}
fun dfs(map:Array<MutableList<Int>>,isCheck:Array<MutableList<Boolean>>,node1: Int,node2:Int) : Int{
var count = 1 // 순회하면서 더해질 count 변수
if(node1 < 0 || node2 < 0 || node1 >= map.size || node2 >= map[0].size || map[node1][node2] == 0 || isCheck[node1][node2]){
return 0
} // 범위 초과 및 이미 방문한 아파트에 대해서는 0을 리턴
if(!isCheck[node1][node2] && map[node1][node2] == 1){ // 방문하지 않은 아파트에 대해서는 아래 dfs 함수 실행
isCheck[node1][node2] = true // 방문 처리
// 상,하,좌,우를 탐색하는 dfs 함수 실행
count += dfs(map,isCheck,node1+1,node2)
count += dfs(map,isCheck,node1,node2+1)
count += dfs(map,isCheck,node1-1,node2)
count += dfs(map,isCheck,node1,node2-1)
/**
* 모두 방문이 가능하면 count에 해당 값들을 더해준다.
*/
return count //탐색이 끝나면 count return
}
return 0
}
🌟 돌아보며
위 코드를 통해 간단한 dfs 개념을 익혀보면 도움이 많이 될 것이다.
진짜 맨 처음에 인접 행렬 또는 인접 리스트로 풀지 않고, 간단하게 data class를 활용해 node에 저장하고 순회하니 방향성을 가진 node에서만 작동해 난감했다.
stack을 활용하거나 인접 리스트를 활용한 풀이를 이해하고 많이 풀어보는 게 좋을 것 같다.
소중한 시간 사용해 긴 글 읽어주셔 감사합니다.
