백준 2644번 촌수계산 Kotlin 구현해보기

---

```

백준 2644번 촌수 계산 Kotlin 구현해보기

```

Kimc Kotlin Study

이번 글을 통해 배워갈 내용

1. 백준 2644번 촌수 계산 풀이

---

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

2644번: 촌수계산

 

 

백준 2644번 촌수계산은

난이도 실버 등급의 문제로서

 

n명의 사람이 주어지고 

x번째 사람과 y 번째 사람의 번호가 주어진 다음

각 사람들 간에 1촌 관계가 주어진 경우

x번째 사람과 y 번째 사람의 촌수를 구해주면 되는 문제입니다.

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

2차원 배열에 모든 촌수를 입력해준 다음

X번째 사람(시작하는 사람부터)

모든 연결된 촌수를 하나씩 가까운 순으로 찾아보고

Y번째 사람이 나오면 해당되는 촌수를 출력하고 종료하면 되는

BFS 문제입니다.

저는 시간 관계상 시간 복잡도가 O(n^2)이지만

visited 배열을 만들어서 복잡도를 줄일 수 있을 겁니다.

 

import java.util.*

fun main(args: Array<String>) {
    // 입력
    val pCnt = readln().toInt()
    val (p1Idx, p2Idx) = readln().split(" ").map { it.toInt() }
    val linkCnt = readln().toInt()
    val distanceMap: Array<IntArray> = Array(pCnt + 1) { IntArray(pCnt + 1) }
    for (i in 1..linkCnt) {
        val (from, to) = readln().split(" ").map { it.toInt() }
        distanceMap[from][to] = 1
        distanceMap[to][from] = 1
    }

    // 출력
    print(bfs(distanceMap, p1Idx, p2Idx, pCnt))
}

fun bfs(distanceMap: Array<IntArray>, p1Idx: Int, p2Idx: Int, pCnt: Int): Int {
    var ans = -1
    val que: Queue<Int> = LinkedList()
    val distanceArr = IntArray(pCnt + 1)
    distanceArr.fill(-1)
    distanceArr[p1Idx] = 0
    que.add(p1Idx)
    while (!que.isEmpty()) {
        val curPIdx = que.poll()
        if (curPIdx == p2Idx) {
            ans = distanceArr[curPIdx]
            break
        }
        for (i in 1..pCnt) {
            if (distanceMap[curPIdx][i] == 1) {
                if (distanceArr[i] == -1) {
                    distanceArr[i] = distanceArr[curPIdx] + 1
                    que.add(i)
                }
            }

        }
    }
    return ans
}
// https://codemasterkimc.tistory.com/

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

---