[Algorithm] 깊이 우선 탐색(DFS,Depth-First-Search)이란? (feat.Swift)

안녕하세요 Foma 👟 입니다!

 

오늘은 알고리즘 문제에서 엄청 빈번하게 출제되고 알아두면 정말 유용한 DFS에 대해서 알아보도록 하겠습니다.

 

바로 시작할게요!

---

DFS란?

 

"깊이 우선 탐색은 맹목적 탐색 방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다." - 위키 백과 -

 

이게 뭔말이야....;;;

 

쉽게 예제를 통해서 설명드리겠습니다.

 

아래 사진과 같이 지구 안에 세 나라만 있고 모든 나라와 나라의 도시들을 탐색한다고 가정하겠습니다.

 

 

어떤 사람은 "난 먼저 어떤 나라들이 있는지 부터 확인하고 그 나라 안에 있는 도시들을 확인할래" 라고 할 수 있고

 

 

어떤 사람은 "난 먼저 한 나라부터 모든 도시를 확인하고 그 다음 나라로 넘어갈래" 라고 할 수 있습니다.

 

 

이 둘 중에 DFS는 어떤 것 일까요?

 

바로 두 번째 방식입니다. (첫 번째 방식은 BFS 입니다.)

 

지구 -> 한국 -> 서울 이 순서대로 각 정점의 깊이를 먼저 확인했죠?

 

바로 이것을 깊이를 우선 탐색한다. 즉, 깊이 우선 탐색 DFS 방식입니다.

 

만약 서울 안에 구까지 있었다면 아래 사진처럼 점점 더 깊게 확인하다가 더 이상 자식이 없는 경우에

 

강남 -> 마포 -> 은평 옆(너비)으로 확인하는 것이죠.

 

 

탐색하는 순서는 아래와 같이 진행됩니다.

 

 

보통 재귀호출로 구현하지만 단순하게 스택으로 구현할 수 도 있습니다.

---

코드 구현

 

이제 코드로 확인해볼까요?

 

먼저 정점의 갯수를 설정해줍니다.

 

let n:Int = 13

각 정점에 대한 이름을 순서대로 넣어줍니다.

 

let world = ["지구","한국","미국","영국","서울","부산","광주","뉴욕","LA","시카고","런던","맨체스터","리버풀"]

 

지구 = 0 ,

한국 = 1, 미국 = 2, 영국 = 3,

서울 = 4, 부산 = 5, 광주 = 6,

뉴욕 = 7, LA = 8, 시카고 = 9,

런던 = 10, 맨체스터 = 11, 리버풀 = 12 

 

로 해당 이름 인덱스를 연결로 세팅해줍니다.

 

let allConnections:[[Int]] = [
    [0,1],
    [2,0],
    [0,3],
    [4,1],
    [5,1],
    [1,6],
    [3,7],
    [3,8],
    [9,3],
    [2,10],
    [2,11],
    [12,2]
]

 

 

각 인덱스에 자식들이 담기도록 n 크기의 이중배열을 만들어줍니다.

 

 

var parentChildren:[[String]] = Array(repeating: [], count: n)

 

최대 연결될 수 있는 n*n 크기의 이중 배열을 만들어줍니다.

 

var connections[[Bool]] = Array(repeating: Array(repeating: false, count: n), count: n)

 

그리곤 위의 connections에서 서로 연결되어 두 정점을 true로 바꿔줍니다.

 

이렇게 하면 서로 연결되어 있는 것들만 true로 되겠죠?

 

func setConnections() {
    for connection in allConnections {
        let left = connection[0]
        let right = connection[1]
        connections[left][right] = true
        connections[right][left] = true
    }
}

 

for문을 이용해서 현재 정점과 모든 인덱스를 비교합니다.

 

이 중 연결되어 있는 정점 중 부모가 아닌 정점은 자식이란 의미이므로

 

parentChildren의 현재 정점 인덱스 배열에 연결된 정점을 자식으로 추가해줍니다.

 

그리곤 부모를 현재 정점으로 현재를 연결된 정점으로 재귀해줍니다.

 

func searchByDFS(parent:Int,current:Int) {
    connections[current]
        .enumerated()
        .filter{$0.element == true && $0.offset != parent}
        .forEach {
            parentChildren[current].append(world[$0.offset])
            searchByDFS(parent: current, current: $0.offset)
        }
}

 

모든 연결을 하고 정점 0부터 DFS를 실행 시켜준 뒤 parentChildren의 각 인덱스 별 자식들을 확인해보면

 

[["한국", "미국", "영국"], ["서울", "부산", "광주"], ["뉴욕", "LA", "시카고"], ["런던", "맨체스터", "리버풀"], [], [], [], [], [], [], [], [], []]

 

위와 같이 각 정점에 대한 자식들이 저장되어 있는 것을 볼 수 있습니다.

 

setConnections()
searchByDFS(parent: 0, current: 0)
print(parentChildren)
for (i,children) in parentChildren.enumerated(){
    print("\(world[i])의 자식은 \(children)")
}

/*
[["한국", "미국", "영국"], ["서울", "부산", "광주"], ["뉴욕", "LA", "시카고"], ["런던", "맨체스터", "리버풀"], [], [], [], [], [], [], [], [], []]
지구의 자식은 ["한국", "미국", "영국"]
한국의 자식은 ["서울", "부산", "광주"]
미국의 자식은 ["뉴욕", "LA", "시카고"]
영국의 자식은 ["런던", "맨체스터", "리버풀"]
서울의 자식은 []
부산의 자식은 []
광주의 자식은 []
뉴욕의 자식은 []
LA의 자식은 []
시카고의 자식은 []
런던의 자식은 []
맨체스터의 자식은 []
리버풀의 자식은 []
*/

---

전체 코드

 

---

관련 문제

 

프로그래머스 여행 경로

 

코딩테스트 연습 - 여행경로

 

프로그래머스 네트워크

 

프로그래머스 네트워크 Swift

 

프로그래머스 모두 0으로 만들기

 

[Swift] 프로그래머스 월간 코드 챌린지 2 모두 0으로 만들기