/kotlin_algorithm

kotlin 코테 일주일 벼락치기 레츠고

Primary LanguageKotlin

Kotlin Cheat Sheet for Algorithm

Queue(Linked List)

  1. 추가

    • add() : Capacity 인한 오류 발생 시 Exception이 발생
    • offer() : exception 발생 X
      • cf) LinkedList의 경우 capacity제한이 발생하기 어렵기 때문에 어떤것을 써도 상관 없음

  2. queue front값 조회

    • element() : 값이 없으면 NoSuchElementException 발생
    • peek() : null 리턴

  3. 삭제

    • removeFirst() : BFS에서 while문 내부에서 자주 사용할 수 있음
    • remove() : 더이상 빼낼 데이터가 없을 경우 NoSuchElementException을 발생
    • poll() : 더이상 빼낼 데이터가 없을 경우 null 리턴

  4. 예제 코드

val queue = LinkedList<Pair<Int, Int>>()
queue.add(sx to sy)
dist[sy][sx] = 0

while (queue.isNotEmpty()) {
    val x = queue.peek().first
    val y = queue.peek().second
    queue.removeFirst() // remove랑 같은듯


    for (i in 0 until 4) {
        val nx = x + dx[i]
        val ny = y + dy[i]

        if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue

        if (map[ny][nx] != 0 && dist[ny][nx] == -1) {
            queue.add(nx to ny)
            dist[ny][nx] = dist[y][x] + 1
        }
    }
}