[백준] (Swift) 15661번 - 링크와 스타트 (feat. DFS, 완전탐색, 백트래킹)

🟠 문제

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

15661번: 링크와 스타트

 

🟠 풀이 ... 왜 어렵지 ㅠㅠ 

이전에 풀었던 문제 '14889번 스타트와링크'과 동일하다. 단, 조건이 조금 달라졌다. 이전 문제에서는 스타트팀 인원과 링크팀의 인원이 동일했지만 이번 문제에서는 인원이 1명 이상만 있으면 팀구성이 가능하다. 이부분에서 조금 헤맸던것 같다 ㅠㅠ  (도대체 재귀를 어케 돌려야해?)

우선,, 다양하게 그림을 그려가면서 재귀를 생각해보았다. 그리고, dfs를 끊을 조건을 어떻게 구성할지도 생각이 필요했다. (위에는 차근차근 정리하면서 재귀를 생각했느넫 아니라고 판단된 애들..)

💁🏻 먼저 백트래킹 조건을 생각해보자

팀원을 선택할 수 도 있고 안선택할 수도 있다. 이전 풀이에서 작성한 dfs는 dfs로 넘겨지는 인원은 visited = true처리를 하게 끔 되어있다. 여기부분을 바꿔야만 한다. (팀원을 선택하지 않고 dfs를 돌려줘야한다.)

1️⃣ 첫번째 조건은, depth가 n과 동일할떼 dfs함수를 return 해주어야한다.

depth가 n과 동일하다는 것은, 모든 인원을 다 훑어봣다(?)는 의미이기 때문이다. 모든 사람이 visited = true가 아니기 때문에, depth와 n을 비교한다.

if depth == n { // 트리의 깊이가 n이라는것은, n번 다봤다는 뜻
    return
}

2️⃣ 두번째 조건은, 팀 인원을 살펴줘야한다.

팀 인원은 1명~n-1명까지구성이 가능하다. 그래서 지금 visited = true인 팀원이 한명일 때, 두명일 때, 세명일때,,,, 이렇게 봐주면 된다! 말그대로 완전탐색으 해주는 것이다.

if team == total { ..여기서 teamStart, teamLink 계산.. }

 

위 조건들은 전부 func 매개변수로 넘겨줄 것이다. 그렇게 전체 작성한 나의 코드는 다음과 같다.

private func dfs(depth: Int, team: Int, total: Int) {
    if depth == n { // 트리의 깊이가 n이라는것은, n번 다봤다는 뜻
        return
    }

    if team == total {
        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
    }

    visited[depth] = true
    dfs(depth: depth + 1, team: team + 1, total: total)
    visited[depth] = false
    dfs(depth: depth + 1, team: team, total: total)
}

for k in 1..<n {
    dfs(depth: 0, team: 0, total: k)
}

print(minResult)

이렇게 해도 무사히 통과가 된다.

 

🟠 더 좋은 코드

인터넷에서도 다들 비슷한 방식으로 풀었다. 근데, 내가 한가지 놓친 것이 있었다. 우리는 어쨌든 '두 팀의 차이'만 비교하면 된다. start팀이 3명인지, link팀이 3명인지 중요하지 않다! 그래서, start = 1과 link = 234가 팀인 경우랑, start = 234와 link -=1 이 팀인 경우를 봤을 때, 두 개의 답은 같게 나올 것이다. 그래서,, total 부분을 0부터 n까지 for문을 돌리지 않고 n/2+1까지 돌려주는 것이 더 효율적이다.

실제로 범위를 수정하고 동일한 코드를 돌리니, 시간이 반으로 줄었다.

for k in 1..<n/2+2 {
    // true인 팀이 1개일때부터 n/2개일때까지 비교
    dfs(depth: 0, team: 0, total: k)
}