[Swift][DFS][LV_2][프로그래머스] 배달

요구능력 : DFS에 대한 이해

 

코드설명 : 

 

주의: 이 해설은 32번 케이스를 통과하지 못했습니다.

DFS로는 도저히 32번을 통과못할것 같지만 풀이가 궁금하신 분들이 계실것같아 올렸습니다.

다음번에 BFS로 풀어보고 따로 글 올리겠습니다.

 

간선과 가중치가 주어진 문제로 연결그래프를 만들고 그 그래프를 타고가는 방식으로 코드를 짜면된다.

1. 연결그래프 작성

주어진 간선과 가중치를 튜플을 이용해서 연결그래프에 함께 담았다.

 for i in 0..<road.count{
        graph[road[i][0]].append((road[i][1], road[i][2]))
        graph[road[i][1]].append((road[i][0], road[i][2]))
    }

 

2. DFS

참고로 문제에서는 주문받을수 있는 마을의 개수를 리턴하라고 했는데, 만약 배열그대로 리턴하면 마을이 주문받을 수 있는 경우가 여러개라서 마을이 여러번 들어간다. 따라서 Set을 이용해서 마을이 중복적으로 들어오는 부분을 예방(?)했다.

그리고 1을 먼저 넣어주고 방문처리해주는 이유는 graph[1]부터 돌게되면 1은 이미 방문이 되어있어야 한다.

문제에서는 1부터 출발이라고 했으므로 1은 다시방문 하지 않아야한다.(어차피 연결그래프를 중복으로 다시돌지 않으려면 방문처리를 해놔야함)

count에 마을을 가는데 걸리는 시간을 담아줬는데, count가 k보다 커지면 return해줌으로써 쓸데없는 루프를 막는다.

참고로 i.0은 현재 방문하는 정점이고 i.1은 그 정점을 방문할 때 걸리는 시간이다.

count가 k보다 작거나 같을때에는 result에 insert를 해준다.

이전 마을에서 방문한 마을까지 걸리는 시간을 더 했을때 count가 k보다 작거나 같을 때는 문제의 조건을 만족하기 때문이다.

이렇게 되면 방문한 마을은 k시간이하로 방문이 가능하다는 의미이기때문.

dfs()에 현재방문한마을을 넣어주고 연결그래프를 계속 돌다가 count가 k가 넘어가면 return되는것이다.

result.insert(1)
    
    func dfs(_ start: Int){
        visited[start] = true
        for i in graph[start] {
            if count > k {
                return
            }
            if !visited[i.0]{
                visited[i.0] = true
                count += i.1
                if count <= k {
                    result.insert(i.0)
                }
//                print("\(start) -> \(i.0) : \(count)")
                dfs(i.0)
                visited[i.0] = false
                count -= i.1
            }
        }
        
        
    }

 

후기 : DFS로 간선과 가중치(?)를 한꺼번에줘서 애좀먹었다..

32번 테스트케이스는 시간초과 나머지는 통과했다.

다음번에는 BFS로 풀어야지..

func solution(_ N:Int, _ road:[[Int]], _ k:Int) -> Int {
    var visited = Array(repeating: false, count: N + 1)
    var result = Set<Int>()
    var graph: [[(Int,Int)]] = Array(repeating: [], count: N + 1)
    var count = 0
    for i in 0..<road.count{
        graph[road[i][0]].append((road[i][1], road[i][2]))
        graph[road[i][1]].append((road[i][0], road[i][2]))
    }
    result.insert(1)
    
    func dfs(_ start: Int){
        visited[start] = true
        for i in graph[start] {
            if count > k {
                return
            }
            if !visited[i.0]{
                visited[i.0] = true
                count += i.1
                if count <= k {
                    result.insert(i.0)
                }
//                print("\(start) -> \(i.0) : \(count)")
                dfs(i.0)
                visited[i.0] = false
                count -= i.1
            }
        }
        
        
    }
    
    dfs(1)
//    print(result)
    return result.count
}