[프로그래머스] Swift - 등대

https://school.programmers.co.kr/learn/courses/30/lessons/133500

프로그래머스

 

2023.11.21 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

문제 조건

• n 개의 등대가 존재
• n-1 개의 등대 간선이 존재
• 즉, 그래프 형태이다.
• 한 간선을 구성하는 두 노드 중 한개는 불이 켜져야 한다.
• 불을 켜야하는 등대의 최소 개수를 리턴해야 한다.

 

우선 그래프 문제이기 때문에 그래프 탐색에서 주로 사용되는 DFS, BFS를 생각해볼 수 있습니다.

 

이 문제에서도 결국 불을 켜야 하는 노드들을 찾아야 하는 것인데 다양한 방법이 있을 수 있지만 DFS를 사용했습니다.

 

우선, 어떤 노드에 불을 켤지 조건을 생각해야 했습니다.

여러 간선과 연결된 노드에 불을 켜는 것이 당연히 효율적일 것입니다.

반대로 leaf 노드에 불을 켜게 되면 매우 비효율적입니다.

왜냐하면 자신과 연결된 노드가 parent 노드 1개 밖에 없기 때문에 불열 켰을 때 해결되는 간선의 수가 1개로 매우 적습니다.

따라서 리프 노드와 연결된 간선에 불을 켜고 싶을 때는 parent 노드에 불을 켜야합니다.

 

이 조건을 따라 dfs로 구현을 했습니다

light 배열에 불을 켠 노드들을 기록합니다.

우선 dfs를 사용해 리프 노드들까지 이동합니다.

그리고 다시 부모 노드로 한 레벨씩 올라갑니다.

자식 노드의 불이 꺼져 있고 본인(parent)또한 불이 꺼져 있다면 이 두 노드 중 1개는 불이 켜져야합니다.

➡️ 이 때 앞서 말한 것처럼 부모 노드에 불을 켭니다.

 

어차피 리프노드부터 올라오기 때문에 계속 부모 노드를 선택해서 불을 켜게 되면 모든 간선에 불을 켠 노드가 1개 이상 존재하게 됩니다.

 

 

풀이

solution 함수 구현

func solution(_ n:Int, _ lighthouse:[[Int]]) -> Int {
    
    var graph = [Int: [Int]]()
    
    for edge in lighthouse {
        graph[edge[0], default: []].append(edge[1])
        graph[edge[1], default: []].append(edge[0])
    }
    
    var light = Array(repeating: false, count: n+1)
    var result = 0
    
    func dfs(node: Int, parent: Int) {
        let children = graph[node, default: []]
        
        for child in children {
            if child == parent {
                continue
            }
            
            dfs(node: child, parent: node)
            
            if light[child] == false && light[node] == false {
                light[node] = true
                result += 1
            }
        }
    }
    
    dfs(node: 1, parent: 1)

    return result
}

 

1. 그래프를 딕셔너리로 저장합니다.
2. dfs 함수를 구현합니다.
   1. 현재 노드와 자식 노드 번호를 파라미터로 받습니다.
   2. for문을 돌며 자식 노드들로 내려가게 됩니다.
   3. 같은 노드를 중복 방문하는 것을 막기 위해 child == parent 일 때는 continue를 시켜줍니다.
   4. 자식 노드와 현재 노드 모두 불이 꺼져있다면 현재 노드(부모)의 불을 켜줍니다.
3. dfs를 실행합니다.

 

 

마무리

일반적인 그래프 탐색 DFS 문제와 유사하지만 보통 DFS로 현재 탐색하고 있는 노드에서 로직을 처리하는데 이 문제에서는 리프 노드까지 내려갔다가 다시 올라오면서 로직을 처리해야 했습니다.

(여기서 로직은 불을 켜는 로직)