[백준] 촌수 계산 2644번

지난번 바이러스 문제를 해결한 후 다음으로 BFS 문제에 도전해 보았습니다.

처음 문제를 접했을 때, 그림이 없이 글로만 설명되어 있어서 이해하기가 어려웠습니다.

하지만 처음부터 차근차근 문제를 읽어보고,

예제 입력된 숫자들을 살펴보며 이해하기 시작했습니다. 

 

---

1. 문제 링크

 

2644번: 촌수계산

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

문제 

우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.

여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

 

입력

사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.

각 사람의 부모는 최대 한 명만 주어진다.

 

출력

입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다.

예제 입력

9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

정답 : 3

9
8 6
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

정답 : -1

 

2. 코드

let n = Int(readLine()!)!
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let num1 = input[0]
let num2 = input[1]
let m = Int(readLine()!)!

var graph : [[Int]] = Array(repeating: [], count: n+1)
var visited : [Bool] = Array(repeating: false, count: n+1)      // n+1 갯수만큼 Bool 배열 만듬 방문시 true

for _ in 0..<m{
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    let x = input[0]        
    let y = input[1]        
    graph[x].append(y)      // graph[x] = [y]
    graph[y].append(x)      // graph[y] = [x]
}


print(bfs(graph: graph))


func bfs(graph: [[Int]]) -> Int{
    var queue = [(num1 , 0) ]         // 큐 배열 안에 튜플값을 넣음 ( 값, 가중치 )
    var find : Bool = false           // 발견하면 true
    visited[num1] = true              // 처음 방문은 num1 값으로 지정 -> 어차피 양방향이라 어디서 시작하든 연결되어 있음
    
    while !queue.isEmpty{
        let currentNode = queue.removeFirst()
        
        if currentNode.0 == num2{       // 현재 노드의 값이 num2랑 같다면
            find = true                 // find 값을 true로 바꾸고
            return currentNode.1        // 멈추게 만듬
        }
        
        for node in graph[currentNode.0]{   //currentNode.0의 값은 ex)2이면 graph[2]값도 2인덱스에 있음
            if visited[node] == true{
                continue
            }
            visited[node] = true
            queue.append((node,currentNode.1 + 1))
        }
    }
    return -1
}

 

3. 코드 설명

예제 입력을 받을 때 전체 사람의 수, 촌수를 계산해야 하는 두 사람, 그리고 부모 자식 관계의 개수인 m개를 입력받습니다. 

graph와 방문 여부를 확인하는 배열 visited을 미리 크기를 설정해 주었습니다.

graph는 Array(repeating: [], count: n+1)을 통해 전체 노드의 개수 n+1만큼의 빈 배열 []을 생성합니다. 이를 통해 각 노드에 대한 연결된 노드들을 저장할 수 있습니다.
visited는 Array(repeating: false, count: n+1)을 통해 전체 노드의 개수 n+1만큼을 false로 초기화합니다. 이 배열은 각 노드의 방문 여부를 저장하는 용도로 사용됩니다.

 

바이러스 문제를 풀고 나서 다른 분들의 코드를 살펴보면서 저의 코드와 비교해 본 결과 복잡하고 어렵게 양방향 그래프를 설정하고 있었습니다. 하지만 굳이 그렇게 복잡하게 생각할 필요가 없었습니다.
실제로 그래프를 구성할 때, graph[1]의 값을 찾고 싶다면 graph[1]을 호출하는 것으로도 해당 인덱스에 저장된 값이 나오게 됩니다. 이렇게 단순하게 접근할 수 있어서 코드를 더 간결하게 작성할 수 있게 되었으며 이런 부분을 깨닫게 되었습니다..😅

그래프를 구성한 후에는 queue를 생성합니다. 큐는 튜플 형태로 구성되어 있으며, 초기값으로 첫 번째 사람 num1을 넣고, 촌수를 계산하면서 두 번째 사람 num2까지 도달하면 멈추어야 하므로 찾음 여부를 나타내는 find 변수를 생성하였습니다.

while문을 사용하여 큐를 순환하며 연결된 노드들을 탐색합니다.

각 노드를 방문할 때마다 큐에 queue.append((node, currentNode.1 + 1)) 와 같이 현재 노드와 그래프의 가중치를 함께 저장합니다. 가중치는 현재 노드까지의 촌수를 나타내며 타고 올라갈 때마다 1씩 증가시킵니디.

반복문을 돌면서 현재 탐색 중인 노드의 값이 두 번째 사람 num2와 일치하면 반복문을 멈추고 해당 노드까지의 촌수를 반환합니다.

만약 두 번째 사람을 찾지 못한다면 촌수를 계산할 수 없는 상황이므로 -1을 반환합니다.