[Kotln] 백준 2617 : 구슬 찾기 <Gold4>

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

2617번: 구슬 찾기

Code

---

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

var cntLTH = 0
var cntHTL = 0

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))){
    val (N, M) = readLine().split(" ").map { it.toInt() }

    var graph = Array(N+1, { IntArray(N+1,{0}) })
    repeat(M){
        val (fir, sec) = readLine().split(" ")
        graph[fir.toInt()][sec.toInt()] = 1
        graph[sec.toInt()][fir.toInt()] = 2
    }

    val half = (N+1)/2
    var result = 0
    for (i in 1 .. N.toInt()){
        cntLTH = 0
        cntHTL = 0
        var visitedLowToHigh = BooleanArray(N+1, {false})
        var visitedHighToLow = BooleanArray(N+1, {false})

        dfsLowToHigh(graph, visitedLowToHigh, i)
        dfsHighToLow(graph, visitedHighToLow, i)

        if (cntHTL >= half || cntLTH >= half)
            result++
    }

    val bw = BufferedWriter(OutputStreamWriter(System.out))
    bw.write("${result}")
    bw.flush()
    bw.close()
}

fun dfsLowToHigh(graph: Array<IntArray>, visited: BooleanArray, positon: Int){
    visited[positon] = true

    for (i in 0 until graph[positon].size){
        if (!visited[i] && graph[positon][i] == 1){
            cntLTH++
            dfsLowToHigh(graph, visited, i)
        }
    }
}

fun dfsHighToLow(graph: Array<IntArray>, visited: BooleanArray, positon: Int){
    visited[positon] = true
    
    for (i in 0 until graph[positon].size){
        if (!visited[i] && graph[positon][i] == 2){
            cntHTL++
            dfsHighToLow(graph, visited, i)
        }
    }
}

---

이 문제의 핵심은 해당 구슬보다 가벼운 구슬의 숫자, 무거운 구슬의 숫자를 파악하는 것이다.

뭐 사실 당연하다면 당연한 소리지만, 이거를 파악하는 아이디어가 중요하다. 아래와 같은 순서의 사고 과정을 거쳤다.

 

기록

일단 입력받은 값을 2차원 배열에 넣어주는 것 자체는 동일하다. 여기서 내 아이디어는 1과 2로 무게의 상관관계를 기록하는 것이다.

무게의 관계는 반드시 일방적일 수 밖에 없다. 1>2 이면서 2>1일수는 없다는 것이다. 그렇기 때문에 1 2를 입력받으면 graph[1][2]는 1로, graph[2][1]은 2로 표기한다면 무게의 상관관계를 표기할 수 있다. 그러면 1혹은 2로 표기한 값이 다른 값에 의해서 덮어쓰기 될까 생각할 수 있는데 앞서 말했듯 무게의 관계는 반드시 일방적이다. 1 2가 나온 이상 2 1은 절대 나올 수 없다.

 

탐색

위와 같은 방법으로 기록 해준 후 탐색을 시작한다.

한 공에 대한 내용으로 쭉 탐색을 하는 것이기 때문에 DFS를 사용했다.

 

이때 중요한 것은 두가지 방향으로 DFS를 진행한다는 것이다. 자신보다 무거운 공을 찾는 DFS, 자신보다 가벼운 공을 찾는 DFS.

이렇게 두가지 방향으로 탐색하여 자신보다 무거운 공의 갯수를 체크하고, 자신보다 가벼운 공의 갯수를 체크하여 둘 중 하나라도 (총 공의 갯수+1)/2 보다 클 경우 무게가 중간인 구슬이 될 수 없는 구슬로 판별하고 result의 값을 늘려준다.

 

 

 

생각보다 코드는간단하다. dfsLowToHigh나 dfsHighToLow 내부 코드에 변화를 줘서 하나의 함수를 활용하는 방식으로 구현할 수도 있을 것 같다. 근데 그렇게 되면 코드의 가독성이 떨어질 것 같아서 일단은 분리해두었다.

 

아이디어 자체는 빨리 떠올렸는데 graph관련 알고리즘을 안풀어본지 오래됐다는게 확실히 느껴졌다. 종류별로 풀면서 재활훈련 해야겠어 아주...