<백준> 24.05.29에 푼 문제들

1. DFS와 BFS (Silver 2)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/DFS와 BFS at main · heesoo-park/ForCodeKata

제출 결과

작성한 코드는 다음과 같다.

import java.io.*
import java.util.*

private lateinit var graph: Array<MutableList<Int>>
private lateinit var visited: BooleanArray
private val bw = BufferedWriter(OutputStreamWriter(System.out))

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    
    val (n, m, v) = br.readLine().split(' ').map { it.toInt() }
    graph = Array(n + 1) { mutableListOf<Int>() }
    
    repeat(m) {
        val (s, e) = br.readLine().split(' ').map { it.toInt() }
        graph[s].add(e)
        graph[e].add(s)
    }
    
    for (i in graph) {
        i.sort()
    }
    
    visited = BooleanArray(n + 1)
    dfs(v)
    
    bw.write("\n")
    
    visited = BooleanArray(n + 1)
    bfs(v)
    
    bw.flush()
    bw.close()
}

fun dfs(start: Int) {
    visited[start] = true
    bw.write("$start ")
    
    for (i in graph[start]) {
        if (!visited[i]) {
            dfs(i)
        }
    }
}

fun bfs(start: Int) {
    val q = ArrayDeque<Int>()
    q.add(start)
    visited[start] = true
    
    while (q.isNotEmpty()) {
        val cur = q.removeFirst()
        bw.write("$cur ")
        
        for (i in graph[cur]) {
            if (!visited[i]) {
                visited[i] = true
                q.add(i)
            }
        }
    }
}

(오랜만에 DFS와 BFS라서 좀 오랫동안 머릿속에서 정리하고 코드 작성했다.)

2. 쉬운 최단거리 (Silver 1)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/쉬운 최단거리 at main · heesoo-park/ForCodeKata

제출 결과

작성한 코드는 다음과 같다.

import java.io.*
import java.util.*

data class Pos(
    val row: Int,
    val col: Int,
    val cnt: Int
)

private lateinit var start: Pos

val dy = listOf(0, 1, 0, -1)
val dx = listOf(1, 0, -1, 0)

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val (n, m) = br.readLine().split(' ').map { it.toInt() }
    val map = Array(n) { IntArray(m) }
    val visited = Array(n) { BooleanArray(m) }
    var result = Array(n) { IntArray(m) { -1 } }

    for (r in 0 until n) {
        val row = br.readLine().split(' ').map { it.toInt() }
        for (c in 0 until m) {
            map[r][c] = row[c]
            if (row[c] == 2) start = Pos(r, c, 0)
            if (row[c] == 0) result[r][c] = 0
        }
    }

    val q = ArrayDeque<Pos>()
    q.add(start)
    result[start.row][start.col] = 0
    visited[start.row][start.col] = true

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

        for (i in 0 until 4) {
            val newR = cur.row + dy[i]
            val newC = cur.col + dx[i]

            if (newR !in 0 until n || newC !in 0 until m) continue
            if (visited[newR][newC] || map[newR][newC] == 0) continue

            result[newR][newC] = cur.cnt + 1
            visited[newR][newC] = true
            q.add(Pos(newR, newC, cur.cnt + 1))
        }
    }

    result.forEach { row ->
        row.forEach { land ->
            bw.write("$land ")
        }
        bw.write("\n")
    }

    bw.flush()
    bw.close()
}

(뭔가 그리 깔끔한 코드같지가 않은 느낌...?)

 

3. 겹치는 건 싫어 (Silver 1)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/겹치는 건 싫어 at main · heesoo-park/ForCodeKata

제출 결과

작성한 코드는 다음과 같다.

import java.io.*
import java.util.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val (n, k) = br.readLine().split(' ').map { it.toInt() }
    val nums = br.readLine().split(' ').map { it.toInt() }
    val checked = IntArray(100001)

    var front = 0
    var end = 0
    var maxLen = 0
    while (front < n) {
        if (checked[nums[front]] < k) {
            checked[nums[front]]++
            front++
        } else {
            checked[nums[end]]--
            end++
        }

        maxLen = maxOf(maxLen, front - end)
    }

    bw.write("$maxLen")
    bw.flush()
    bw.close()
}

(투포인터 느낌이 뽝! 와서 해보는데 생각보다 오래 걸림...)