[Swift 알고리즘] 백준 2644 촌수계산

○

DFS/BFS Silver 2

백준 2644 촌수계산

문제
여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.
입력
사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다.
입력 파일의 첫째 줄에는 전체 사람의 수 n
둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호
셋째 줄에는 부모 자식들 간의 관계의 개수 m
넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.
각 사람의 부모는 최대 한 명만 주어진다.
출력
입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때에는 -1을 출력해야 한다.

 

1차시도 - 실패

로직은 대충 맞는데 리턴값을 주면 안됐음. 리턴 값을 주지 말자!

리턴값을 줘버리면 탐색 하나가 끝 노드에 도착하는 순간 -1을 리턴 해버리니까..

func dfs(_ s: Int, _ e: Int, _ sum: Int) -> Int {
    visited[s] = true

    for i in graph[s] {
        if !visited[i] {
            if i == e { return sum }
            return dfs(i, e, sum + 1)
        }
    }
    return -1
}

 

2차시도 - 69108KB 8ms 

DFS를 이용하여 탐색을 해주었다. 원하는 값을 찾고 나면 바로 return을 해주도록! return 안쓰면 12ms 뜨더라. 

완전 쉽게 바로 풀 줄 알았는데 생각보다 시간이 좀 걸렸다.. ㅠ 분발하자

 

풀이방법

1. 입력 받아서 촌수를 저장하는 그래프를 만들어준다. 

2. 방문 여부를 확인하기 위해 visited 배열을 선언해준 후, 결과 값으로 프린트할 result 값을 -1로 초기화해준다.

3. 재귀함수를 사용하여 dfs를 구현해준다. 탈출 조건은 현재 탐색 노드가 end에 도달한다면!

그 외의 경우는 아직 방문 전인 노드를 확인하고 재귀로 탐색을 지속한다. 

4. 출력

let n = Int(readLine()!)!
let input = readLine()!.split(separator: " ").compactMap { Int($0) }
let start = input[0], end = input[1]
let m = Int(readLine()!)!
var graph: [[Int]] = Array(repeating: [], count: n+1)
for _ in 0..<m {
    let input = readLine()!.split(separator: " ").compactMap { Int($0) }
    graph[input[0]].append(input[1])
    graph[input[1]].append(input[0])
}

var visited: [Bool] = Array(repeating: false, count: n+1)
var result = -1

visited[start] = true

func dfs(_ s: Int, _ sum: Int) {
    for i in graph[s] {
        if i == end {
            result = sum
            return
        }

        if !visited[i] {
            visited[i] = true
            dfs(i, sum + 1)
        }
    }
}

dfs(start, 1)
print(result)