[백준/Swift] 9372번: 상근이의 여행

 

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

9372번: 상근이의 여행

 

모든 정점이 연결되어 있기 때문에 한 지점에서 시작해도 모든 경로를 갈 수 있다. 그래서 나는 DFS로 1에서 시작해서 쭉 이동하도록 했다. 그리고 그 경로(edge)의 개수를 세면 된다. 좀 보니까 답이 (정점 개수 - 1) 인 것을 알 수 있다!ㅋㅋㅋ 하지만 DFS로 탐색해 봤다~

 

import Foundation

//input
let t = Int(readLine()!)!
var cnt = 0

func dfs(_ now: Int, _ visited: inout [Bool], _ flights: [[Int]]) {
    visited[now] = true
    for flight in flights[now] {
        if visited[flight] { continue }
        cnt += 1
        dfs(flight, &visited, flights)
    }
}

func solution() {
    let nm = readLine()!.split(separator: " ").map{ Int(String($0))! }
    let (n, m) = (nm[0], nm[1])
    var flights = [[Int]](repeating: [], count: n+1)
    var visited = [Bool](repeating: false, count: n+1)
    for _ in 0..<m {
        let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
        flights[input[0]].append(input[1])
        flights[input[1]].append(input[0])
    }
    dfs(1, &visited, flights)
    print(cnt)
    cnt = 0
}

for _ in 0..<t {
    solution()
}