[백준] (Swift) 14889번 - 스타트와 링크 (두번째 풀이)(feat. DFS, 완전탐색)

🟠 문제

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

🟠 나의 풀이

음,,, 아직 DFS에 대한 개념이 잘 잡히지 않은건가. 역시나 재귀부분을 생각하는데 좀.. 힘들었다.. 도대체 재귀를 어떻게 그렇게 바로바로 생각해내는거지..? 아닌가 다들 나와 같은가?

어쨌든 이번 문제는, 입력받는 N명의 사람들을 1/2로 쪼개서, 더해주는 값에 대한 차이의 최솟값을 구하는 것이다. 우선 방문 여부를 판단해서 계속 조합을 바꿔가며 확인해주어야하기 때문에 DFS 재귀를 사용해서 풀 수 있겠구나 까지 생각할 수 있었다.

N명의 사람이라고 치면, 이미 팀이 구성된 사람은 또 팀을 구성할 수없다. 이것을 방문처리 VIsited배열에 저장했다. 그리고 몇명의 사람까지 도달했는지는 트리의 depth로 판단할 것이다. 한단계씩 재귀를 진행하면서 Depth가 +1씩 증가되고, 이 depth가 n/2가 된다면 dfs를 탈출하도록 만들어야한다. 탈출하기 전에는, visited가 true인 두명을 start팀에 넣어주고, false인 두명을 link팀에 넣어줄 것이다!

이 과정을 그림으로 그려보면서 코드를 구성해보자.

🟠 정답코드

import Foundation

let n = Int(readLine()!)!
var s = [[Int]]()
var visited = Array(repeating: false, count: n)
var minResult = 999999

for _ in 0..<n {
    s.append(readLine()!.split(separator: " ").map{ Int($0)! })
}

private func dfs(depth: Int, start: Int) {
    if depth == n/2 {
        var teamStart = 0
        var teamLink = 0

        for i in 0..<n {
            for j in 0..<n {
                if visited[i], visited[j] {
                    teamStart += s[i][j]
                }

                if !visited[i], !visited[j] {
                    teamLink += s[i][j]
                }
            }
        }
        minResult = min(minResult, abs(teamLink - teamStart))
        return
    }

    for i in start..<n {
        if !visited[i] {
            visited[i] = true
            dfs(depth: depth + 1, start: i)
            visited[i] = false
        }
    }
}

dfs(depth: 0, start: 0)
print(minResult)