[Swift 알고리즘] 프로그래머스(Lv.3) - 양과 늑대 / 2022 카카오 블라인드

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.3) - 양과 늑대" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

코딩테스트 연습 - 양과 늑대

 

---

풀이

이번 문제는 dfs + 완전 탐색 문제입니다.

바로 직전의 문제인 양궁 점수와 비슷한 원리로 해결할 수 있습니다.

 

1. 그래프를 생성합니다.

트리를 만들어야 합니다.

이때, 양방향 그래프가 아닌 단방향 그래프로 구성합니다. (createGraph 메서드)

이 문제에서는 dfs를 탐색할 때 전체 그래프를 이용하지 않습니다.

현재 이동할 수 있는 노드만을 전달하여 탐색합니다. 이유는 아래에서 설명할게요.

 

2. dfs를 실행합니다.

dfs를 실행합니다.

dfs를 호출할 때는 매번 당장 이동할 수 있는 노드만을 전달합니다.

 

저는 처음에 이미 지났던 노드를 지나거나 부모 노드로 이동해야 하기 때문에 양방향 그래프를 사용했습니다.

하지만 그러면 스택이 터지거나 시간 초과가 발생하죠.

 

이 문제의 핵심은 이미 지나간 노드는 다시 방문해도 아무런 변화가 없다는 것입니다.

이미 회수한 양과 늑대이기 때문에 다시 지나가더라도 양과 늑대의 수는 변화가 없죠.

따라서 굳이 양방향으로 만들지 않아도 됩니다. 이 때문에 현재 이동할 수 있는 노드만을 전달하는 것입니다.

[0] -> [1, 8] -> [1, 7, 9] -> ... 이런식으로 전달을 하는 것이죠.

자기 자신으로 이동을 못하기 때문에 자기 자신을 삭제하는 것도 잊으면 안됩니다.

 

노드를 이동할 때마다 양과 늑대의 수를 카운트 하고 양의 수가 많을 때만 노드를 탐색합니다.

 

후기

현재 방문할 수 있는 노드만 전달한다는 아이디어가 정답의 기준이었던 것 같습니다.

화이팅 화이팅입니다.

 

감사합니다!

---

전체 코드

import Foundation

var graph: [Int: [Int]] = [:]
var copyInfo: [Int] = []
var maxSheep: Int = 0

func createGraph(edges: [[Int]]) {
    //단방향 그래프 생성
    for edge in edges {
        if let _ = graph[edge[0]] {
            graph[edge[0]]?.append(edge[1])
        } else {
            graph[edge[0]] = [edge[1]]
        }
    }
}

func dfs(_ canVisit: [Int], wolf: Int, sheep: Int) {
    for node in canVisit {
        let nextWolf = wolf + (copyInfo[node] == 0 ? 0 : 1)
        let nextSheep = sheep + (copyInfo[node] == 0 ? 1 : 0)
        // print("node: \(node) / nextWolf: \(nextWolf) / nextSheep: \(nextSheep)")
        guard nextSheep > nextWolf else {
            continue
        }
        
        maxSheep = max(maxSheep, nextSheep) //최대 양 수
        
        //지금 방문할 수 있는 노드
        var canVisit = canVisit
        let currentIndex = canVisit.firstIndex(of: node)!
        canVisit.remove(at: currentIndex) //자기 자신으로는 못 가므로 제외
        
        canVisit.append(contentsOf: graph[node] ?? []) //기존 + 현재 노드와 연결된 노드
        dfs(canVisit, wolf: nextWolf, sheep: nextSheep)
    }
}

func solution(_ info:[Int], _ edges:[[Int]]) -> Int {
    copyInfo = info
    createGraph(edges: edges)
    
    dfs([0], wolf: 0, sheep: 0)
    
    return maxSheep
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.