포이

7562번 체스판 나이트 말 옮기기

33분 걸림. 와 드디어 코틀린에 적응했나~? 간단한 8방향 BFS 구현이었지만 코틀린으로 bfs 짜서 행복해ㅎㅎ kotlin은 deque도 요상하게 써요…

import kotlin.collections.ArrayDeque

fun main() = with(System.`in`.bufferedReader()) {
    val dx = arrayOf(-1, -2, -2, -1, 1, 2, 2, 1)
    val dy = arrayOf(-2, -1, 1, 2, -2, -1, 1, 2)

    repeat(readLine().toInt()) {
        val l = readLine().toInt()
        val board = Array(l) { IntArray(l) }
        val (currX, currY) = readLine().split(' ').map { it.toInt() }
        val (toX, toY) = readLine().split(' ').map { it.toInt() }

        fun bfs() {
            val q = ArrayDeque<Int>()
            q.add(currX)
            q.add(currY)

            while(q.isNotEmpty()) {
                val x = q.removeFirst()
                val y = q.removeFirst()

                if(x == toX && y == toY) {
                    println(board[x][y])
                    break
                }

                for(i in 0 until dx.size) {
                    if( x + dx[i] >= 0 && x + dx[i] < l) {
                        if( y + dy[i] >= 0 && y + dy[i] < l) {
                            if(board[x+dx[i]][y+dy[i]] == 0){
                                board[x+dx[i]][y+dy[i]] = board[x][y] + 1
                                q.add(x+dx[i])
                                q.add(y+dy[i])
                            }
                        }
                    }
                }
            }
        }

        bfs()
    }

}

python 처럼 (x, y) 튜플을 덱에 넣는건 못함. 대신에 Pair 라는 걸 쓰는 분이 있네

val q: Queue<Pair<Int, Int>> = LinkedList()
    q.add(Pair(x1, y1))
    visited[x1][y1] = true

    while (q.isNotEmpty()) {
        val now = q.poll()
        //현재 위치
        val nx = now.first
        val ny = now.second

와 만들어진 Pair가 아니라 직접 구조체를 구현했음. 이게 더 멋있는데?

data class Knight (
    val x: Int,
    val y: Int,
    val move: Int,
)

val queue: Queue<Knight> = LinkedList()

queue.add(Knight(nowX, nowY, 0))

        while (queue.isNotEmpty()) {
            val cur = queue.poll()

            if (cur.x == toX && cur.y == toY) {
                println(cur.move)
                break
            }

           queue.add(Knight(nextX, nextY, cur.move + 1))

11286번 절댓값 최소힙 구현하기

1시간 걸림. 고민 좀 하다가 양수힙, 음수힙 두개로 하면 되겠구나 생각 들어서 바로 코드 드가자~ 했는데 고려할게 은근히 많아서 pos랑 nag 비교한 다음에 절댓값이 더 작은걸 프린트 하는 것만 신경쓰는 바람에 두번이나 틀림. 사실 print 안한 값은 다시 힙에 도로 넣어줘야하는데 그걸 안해서 계속 틀림. 그리고 나는 코드가 왜이렇게 길지? 다들 어떻게 그렇게 짧게 짠거야ㅠ_ㅠ

import java.util.*  
  
fun main() = with(System.`in`.bufferedReader()) {  
    val maxHeap = PriorityQueue<Int>(reverseOrder())  
    val minHeap = PriorityQueue<Int>()  
    val n = readLine().toInt()  
    var nag = 0  
    var pos = 0  
  
    for(i in 1..n) {  
        val x = readLine().toInt()  
  
        if(x == 0){  
            if(maxHeap.isEmpty() && minHeap.isEmpty()){  
                println(0)  
                continue  
            }  
            if(maxHeap.isNotEmpty()) nag = maxHeap.poll()  
            else nag = 0  
  
            if(minHeap.isNotEmpty()) pos = minHeap.poll()  
            else pos = 0  
  
            if(nag == 0){  
                println(pos)  
                continue  
            }  
  
            if(pos == 0){  
                println(nag)  
                continue  
            }  
  
            if(-nag == pos) {  
                println(nag)  
                minHeap.add(pos)  
            }  
            else if(-nag > pos) {  
                println(pos)  
                maxHeap.add(nag)  
            }  
            else{  
                println(nag)  
                minHeap.add(pos)  
            }  
        }  
        else{  
            if(x < 0) maxHeap.add(x)  
            else minHeap.add(x)  
        }  
    }  
}

아 이게 print 안할거면 poll을 그러니까 리턴 후 삭제 하는게 아니라 peek로 리턴만 했어야했네;; 그리고 continue 안하게 이렇게 짤 수도 있었을텐데 모지리…

repeat(n) {
        val num = x_array[it]
        if (num > 0) {
            plus_queue.offer(num)
        }
        else if (num < 0) {
            minus_queue.offer(num)
        }
        else {
            val ms = minus_queue.size
            val ps = plus_queue.size
            if (ms + ps == 0)
                println(0)
            else if (ms == 0)
                println(plus_queue.poll())
            else if (ps == 0)
                println(minus_queue.poll())
            else {
                if (abs(minus_queue.peek()) > plus_queue.peek()) {
                    println(plus_queue.poll())
                } else
                    println(minus_queue.poll())
            }
        }
    }

많은 사람들이 그냥 `PriorityQueue(compareBy({ it.absoluteValue})) 로 해서 짰는데? 이게 kotlin스럽게 짜는건가;; 오? python은 튜플로 넣네? (abs(x), x) 이렇게 그렇게 heappop할때는 [1] 로 꺼내서 프린트함

1) val maxHeap = PriorityQueue(compareBy<Data> { it.absolute }.thenBy { it.value })
data class Data(
    val absolute: Int,
    val value: Int
)
2) val queue = PriorityQueue<Int>(compareBy({ it.absoluteValue }, { it 
3)     val queue = PriorityQueue<Int> { first, second ->
        val firstAbs = abs(first)
        val secondAbs = abs(second)
        
        if(firstAbs != secondAbs) {
            firstAbs.compareTo(secondAbs)
        } else {
            first.compareTo(second)
        }
    }
4) val pq = PriorityQueue<Int> { a, b -> if (abs(a) == abs(b)) a - b else abs(a) - abs(b) }

kotlin도 python tuple처럼 이렇게 절대값 최소힙 사용 가능 와 정렬하는 법이 너무 다양해서 혼이 나갈것 같아요;; a, b 가 기본적으로 최소힙이라 a < b 인듯. a - b 의 의미는 a(작은게)가 먼저

11403번 경로 찾기

방향 그래프 i -> j 의 간선(1로 표시) 인접행렬이 주어진다. i -> j 를 직접적으로 가지 않고 경유하더라도(i에서 j로 가는 길이 양수면) i에서 j로 갈 수 있다면 1로 갱신하여 인접행렬을 출력한다. 1시간 걸림. 처음엔 어떻게 푸나 했는데
만약 a -> c 가 1이고 a -> a 가 0 이면
그리고 c -> a 가 1 이면
a -> a 는 1이 된다.
그러니까 출발지를 계속 기억해야함. 그래야
a에서 출발한 모든 것은 c -> 도착지 이면
a -> 도착지는 다 1로 바꿔줘야되거든
포문은 그래서 전체 정점을 다 돌아야함.
그래서 그 정점에서 갈 수 있는 모든 곳을 찾아서 갱신해주면 됨.
그럼 graph[start] 행은 끝남. 더 갱신 못함. visited 를 써야할지 말아야할지 생각했는데 j(경유지) 한번 add 했으면 그건 이미 사용한 거니까 더 돌면 시간 낭비라서 visited 써줫음. graph의 요소가 List로 생기기 때문에 List는 값을 재할당 못해서 toArray()로 바꿀려했으나 deplicated된 함수라서 toIntArray()로 바꿔줘야했다

import kotlin.collections.ArrayDeque  
  
fun main() = with(System.`in`.bufferedReader()) {  
    val n = readLine().toInt()  
    var graph = Array(n) { readLine().split(' ').map { it.toInt() }.toIntArray() }  
  
    fun bfs(start : Int) {  
        val q = ArrayDeque<Int>()  
        val visited = BooleanArray(n) { false }  
        q.add(start)  
  
        while(q.isNotEmpty()) {  
            val via = q.removeFirst()  
  
            for(j in 0 until n) {  
                if(graph[via][j] == 1 && visited[j] == false ) {  
                    graph[start][j] = 1  
                    visited[j] = true  
                    q.add(j)  
                }  
            }  
        }  
    }  
  
    for(vertex in 0 until n) {  
        bfs(vertex)  
    }  
  
    for(row in graph) {  
        println(row.joinToString(" "))  
    }  
}

경유지 k와 i, j 를 삼중 포문으로 돌리는게 더 빠르네ㄷㄷ 10^6 이라서 그런가?

    for (k in 0 until n) {
        for (i in 0 until n) {
            for (j in 0 until n) {
                if (arr[i][k] == 1 && arr[k][j] == 1) {
                    arr[i][j] = 1
                }
            }
        }
    }

    val sb = StringBuilder()
    for (i in arr.indices) {
        for (j in arr[0].indices) {
            sb.append("${arr[i][j]} ")
        }
        sb.appendLine()
    }

    println(sb.toString())

아 이게 플로이드-워셜 알고리즘이구나~ https://chanhuiseok.github.io/posts/algo-50/ 문제 풀기 싫을 때 동빈나님 유튜브나 쏵 보자…

11660번 2차원 배열 구간합 구하기

이거 저번에 푼 문제 아닌가? [[7일차 백준#^00a41c]] 2167번이랑 완전 똑같은거 같은데 이건 왜 실버1문제지? 알 수가 없군ㅋ_ㅋ dp 쓸때 첫번째 값은 0으로 초기화해야하는 거 까먹어서 n+1개 2차원 배열로 다시 선언함.

fun main() = with(System.`in`.bufferedReader()) {  
    val (n, m) = readLine().split(" ").map { it.toInt() }  
    val graph = Array(n) { readLine().split(" ").map { it.toInt() }.toIntArray() }  
    val dp = Array(n+1) { IntArray(n+1) }  
  
    for(i in 1..n) {  
        for(j in 1..n) {  
            dp[i][j] = graph[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]  
        }  
    }  
  
    repeat(m) {  
        val (x1, y1, x2, y2) = readLine().split(' ').map { it.toInt() }  
  
        println(dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1])  
    }  
}

내껀 왜 이렇게 남들보다 느리징?ㄷㄷ 2배는 느린듯 출력할때 BufferedWriter 라는걸 안써서 그런가?

//이런식으로 dp를 초기화할 수도 있음.
    var listArr : ArrayList<MutableList<Int>> = ArrayList()
    
    listArr.add(MutableList(num1+1){0})
    
    for(i in 0..<num1){
        listArr.add(("0 " + readLine()).split(" ").map { it.toInt() }.toMutableList())
    }

dp row랑 col 둘다 0으로 초기화하는법! 둘다 MutableList로 선언하기… 즉 ArrayList

    val sb = StringBuilder()
    repeat(m) { i ->
        val (x1, y1, x2, y2) = input[i]
        sb.appendLine(dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1])
    }

    println(sb.toString())

StringBuilder 라는 걸로 한번에 담아둔뒤에 m개를 한번에 출력하네~ 그럼 나보다 훨씬 빠름;;