[Swift][DFS] 백준 10971번 (외판원 순회 2)

요구능력 : DFS에 대한 이해

 

코드설명 : 

 

문제의 입력에는

4

0 10 15 20

5 0 9 10

6 13 0 12

8 8 9 0

가 적혀있다.

 

나처럼 이해못하는 사람을 위해서 해석해보자면,

도시가 4개 있는데, 

1번도시는

1번에서 1번가는데 비용이 0

1번에서 2번가는데 비용이 10

1번에서 3번가는데 비용이 15

1번에서 4번가는데 비용이 20

이런식이다.

 

문제를 이해하고, 이 부분을 본다면 DFS와 인덱스를 이용해서 접근해야겠다고 생각이 든다.

 

1. 우선 입력을 쭉 받아놓는다.

let n = Int(String(readLine()!))!
var w: [[Int]] = Array(repeating: [], count: n)
for i in 0..<n{
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    w[i] = input
}

 

2. 방문여부 저장할 변수 선언

"단, 한 번 갔던 도시로는 다시 갈 수 없다."라는 문제의 조건에 의해 방문여부를 체크해줘야한다.

 

3. dfs함수 설명

인자부터 설명하면 depth는 도시를 방문한 횟수, now는 현재 위치한 도시, start는 시작 도시의 인자이다.

 

1) 탐색의 종료조건 설정

문제에서 "이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다"라고 했으므로 도시는 n번만 방문하면된다. 그리고 start(시작도시)와 now(현재 위치한도시)가 같으면 한번의 탐색을 종료한다.

if depth == n && now == start {
        result = min(result, sum)
        return
    }

 

2) DFS 순회

방문여부를 체크해서 방문하지 않았을 때, 그리고 다음에 방문할 도시의 비용이 0보다 크다면(0인경우 자기자신을 탐색하는 경우니까 이 경우는 탐색하면 안된다 자기 자신을 탐색하게 되면 총 4번 탐색중 1 -> 2 -> 2 -> 3 -> 1 이런식으로 자기자신을 2번도는 경우가생김)

visited[i] = true 해주고,

sum에 다음번에 방문해야하는 곳을 더해준다.

 

여기서 중요한부분은 방문했다고 dfs를 무작정 돌게되면 시간초과가 나게된다.

sum이 result보다 작거나 같아야지만, 탐색을 진행한다.

result는 문제에서 구하고자하는 "원판원의 순회에 필요한 최소비용"을 저장할 것인데,

sum이 result보다 크면 그건 최소값이 아니기 때문에 이후 탐색을 진행할 필요가 없다.

탐색을 진행한다면 시간이 많이 추가된다.

 

 

방문한곳에서 나왔으면 false처리 해주고

방문한곳에서 나왔으니까 sum에서 다음 방문한곳을 빼준다.

for i in 0..<n {
        if !visited[i] && w[now][i] > 0{
            visited[i] = true
            sum += w[now][i]
            if sum <= result{
                dfs(depth + 1, i, start)
            }
            visited[i] = false
            sum -= w[now][i]
        }

 

그리고 어느곳에서 출발하던 최소값은 똑같다.

한 도시씩 전부 다 돌기 때문이다.

 

후기 : 이 문제는 문제를 이해하는게 더 어려웠다..

문제를 이해하니까 그냥 DFS를 사용하라는 문제였다.

실버2보단 골5정도이지않나...

let n = Int(String(readLine()!))!
var w: [[Int]] = Array(repeating: [], count: n)
for i in 0..<n{
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    w[i] = input
}

var depth = 0
var result = Int.max
var sum = 0


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


func dfs(_ depth: Int, _ now: Int, _ start: Int) {
    if depth == n && now == start {
        result = min(result, sum)
        return
    }
    for i in 0..<n {
        if !visited[i] && w[now][i] > 0{
            visited[i] = true
            sum += w[now][i]
            if sum <= result{
                dfs(depth + 1, i, start)
            }
            visited[i] = false
            sum -= w[now][i]
        }
    }
}

dfs(0, 0, 0)

print(result)