[백준] BOJ 14466 소가 길을 건너간 이유 6 (골드 3)

문제

---

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

14466: 소가 길을 건너간 이유 6

---

해설

---

1. 일반 BFS를 수행하면
   1. 길을 이용하지 않으면 돌아가야하는 경우 vs 길을 이용하면 더 빨리 도달할 수 있는 경우
   2. 위의 상황에 길을 무조건 타는 것이 최소경로이므로 길을 타게 되어 틀린 답을 내놓게 된다고 생각함.
2. 따라서, PQ를 통해 Info객체의 compareTo를 재정의하여 Info의 멤버변수인 isRoad(길을 사용한적 있는지)에 따라 이용한적 없는 객체를 우선순위를 높힘
3. 또한, 소 a, b, c, d, e가 있을 때 문제는 쌍 의 개수를 구하는 것이므로 a-b == b-a이다.
4. 이러한 모든 쌍을 확인하기 위해 각 소의 위치 에서 BFS를 수행하여본다.
5. 앞서 말한 것처럼 a-b == b-a이므로 중복 제거가 필요함을 인지 → 중복 제거를 위해 전역 cowMap(Map자료구조)를 통해 BFS의 시작점으로 사용된 소는 삭제해준다. (cowMap은 입력과 동시에 초기화)
   1. 여기서 주의할점 : Map<Int, List<Int>로 하지 않으면 (3,3 : Key - 3,2 : Value), (3,3 : Key - 2,3 : Value) 이런식으로 입력이 들어오면 하나의 키에 2개의 길이 매핑되어야하는데 한개만 되므로 주의
   2. 이 과정에서 x, y 좌표를 키로 사용하려면 객체 사용 or flat하게 변경하여 Integer사용 2가지 방법 중 후자를 택했다. (최대 100 * 100 이므로)
6. PQ를 통한 BFS를 수행하며,
   1. 길을 한번이라도 사용하고 현재 좌표에 도달한 경우
   2. 길을 한번도 사용하지 않고 온 경우
   3. 2가지의 경우가 있다고 판단하여 isv배열을 [x][y][0, 1]로 두어 0은 길 사용 X, 1은 길 사용 O로 방문처리
   4. 또한, isv[0] == true인 경우 isv[1]은 의미가 없어진다고 생각하여 isv[0]일때도 isv[1] = true로 세팅해줌 (길을 안쓰고 올 수 있는데 쓰면서 온 경우를 굳이 체크할 필요가 없다고 판단)
7. 위 과정을 수행하면 a, b, c, d 의 소가 있다면
   1. a → b, c, d와 길 사용 여부 체크 (a를 cowMap에서 삭제)
   2. b → c, d (a는 cowMap에서 삭제되었기 때문에 고려 X)
   3. c → d
   4. 이러한 과정에서 길을 사용하고 도달한 경우에는 res 변수를 ++해주어 카운팅
8. 또한, 조금이라도 시간을 줄여보고자 BFS메서드 내부에 만난 소를 카운팅해주어 현재 cowMap에 있는 소의 마리수 == 만난 소 카운트 이면 메서드를 탈출한다. (cowMap에 있는 소를 모두 만나면 더 탐색할 필요가 없으므로)

---

코드 (BFS)

---

import java.io.*
import java.util.ArrayList
import java.util.PriorityQueue
import java.util.StringTokenizer

var N = 0
var K = 0
var R = 0
var res = 0
var dx = arrayOf(-1, 1, 0, 0)
var dy = arrayOf(0, 0, -1, 1)
lateinit var roads: HashMap<Int, ArrayList<Int>>
lateinit var cowMap: HashMap<Int, Boolean>

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {

    var st = StringTokenizer(readLine())
    N = st.nextToken().toInt()
    K = st.nextToken().toInt()
    R = st.nextToken().toInt()

    roads = HashMap()
    for (i in 0 until R) {
        st = StringTokenizer(readLine())
        var x1 = st.nextToken().toInt() - 1
        var y1 = st.nextToken().toInt() - 1
        var x2 = st.nextToken().toInt() - 1
        var y2 = st.nextToken().toInt() - 1
        var list = roads.getOrDefault(flat(x1, y1), ArrayList<Int>())
        list.add(flat(x2, y2))
        roads.put(flat(x1, y1), list)

        list = roads.getOrDefault(flat(x2, y2), ArrayList<Int>())
        list.add(flat(x1, y1))
        roads.put(flat(x2, y2), list)
    }

    cowMap = HashMap()
    var cows = Array(K, {
        st = StringTokenizer(readLine())
        var x = st.nextToken().toInt() - 1
        var y = st.nextToken().toInt() - 1
        cowMap.put(flat(x, y), true)
        arrayOf(x, y)
    })

    for (i in 0 until K) {
        //a 소에서 b, c, d, f로 가는 경우 == b, c, d, f에서 a로 가는 경우 이므로 탐색의 시작점으로 사용된 소는 맵에서 삭제 (중복 제거)
        //또한 자기 자신의 위치를 지우고 시작
        cowMap.remove(flat(cows[i][0], cows[i][1]))
        //각 소의 위치에서 bfs탐색
        bfs(cows[i][0], cows[i][1])
    }
    println(res)
}

fun bfs(x: Int, y: Int) {
    var pq = PriorityQueue<Info>()
    //3차원 visit 배열 [0] : 다리 안건넘. [1] : 다리 건넘
    var isv = Array(N, { Array(N, { BooleanArray(2, { false }) })})

    pq.offer(Info(x, y, false))

    isv[x][y][0] = true
    isv[x][y][1] = true
    var cows = HashSet<Int>()

    while (!pq.isEmpty()) {
        val info = pq.poll()

        //현재 위치가 소일때
        if (cowMap.getOrDefault(flat(info.x, info.y), false) && cows.add(flat(info.x, info.y))) {
            if(info.isRoad) {
                res++
            }
            if(cows.size == cowMap.size) return
        }
        var idx = if(info.isRoad) 1 else 0
        for (i in 0 until 4) {
            var nx = info.x + dx[i]
            var ny = info.y + dy[i]

            if (isOutRange(nx, ny)) continue
            //길을 타고, 안타고 동일하게 도착한적 있으면 스킵
            if (isv[nx][ny][idx]) continue
            //가려는 곳이 길을 타고왔을 때 (info.isRoad), 길을 타고 가는지 (맵에서 가려는 곳, 온 곳이 같을 때)
            var list = roads.getOrDefault(flat(nx, ny), null)
            var road = list?.any {it == flat(info.x, info.y)} ?: false //해당 위치에서 길이 있으면서 info.x, y와 연결된 길이라면 true, null이거나 없으면 false
            var isRoad = info.isRoad || road

            pq.offer(Info(nx, ny, isRoad))
            isv[nx][ny][if(isRoad) 1 else 0] = true
        }
    }
}

fun isOutRange(x: Int, y: Int) : Boolean {
    return x < 0 || y < 0 || x >= N || y >= N
}

fun flat(x : Int, y : Int): Int {
    return x * N + y
}

class Info(val x: Int, val y: Int, val isRoad: Boolean): Comparable<Info> {
    override fun compareTo(other: Info): Int {
        var num1 = if(this.isRoad) 1 else -1
        var num2 = if(other.isRoad) 1 else -1
        return Integer.compare(num1, num2)
    }
}

---

결론

---

코틀린을 공부해보고 싶어서 코틀린으로 해결해봤다!

익숙하지 않아서 오래 걸린 것 같다..

---