개발해요

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

풀이

그래프의 모든 노드를 인접한 노드와 같은 집합에 속하지 않도록 하면서, 두 집합으로 분할할 수 있는지 판별하는 문제이다.

먼저 노드를 두 집합으로 분할해야 하므로, 모든 노드를 방문하면서 어떤 집합에 속할 것인지를 정해준다. 분할하는 것을 쉽게 색칠한다고 표현하자. DFS나 BFS를 사용해서 노드를 한번씩만 방문하면서 인접 노드를 현재 노드와 다른 색으로 색칠하면 된다. 나는 colors라는 배열을 만들어서 모든 노드를 0과1로 나누었다. 

얼핏 단순하게 "인접 노드를 모두 다른 색으로 칠하면 무조건 이분 그래프로 만들 수 있는 거 아닌가?"라고 생각할 수도 있지만, 인접노드가 이미 이전에 방문되었고, 현재 노드와 같은 색으로 칠해진 경우가 발생할 수 있다.

분할이 끝나면 그래프에서 모든 노드를 돌면서 자신과 같은 색인 인접노드가 있는지 확인해주면 이분 그래프인지 아닌지 판별할 수 있다.

참고로 연결 그래프라면 DFS나 BFS를 사용해서 노드를 한번씩만 방문하면서 이분 그래프 여부를 판별할 수 있으며, 연결 그래프가 아니라면 위에 언급한 대로 노드마다 인접 노드를 검사해주면 된다.

이를 좀 더 구체적으로 적으면 다음과 같다.  

1. DFSorBFS를 사용해서 모든 노드를 한번씩 방문한다.

2. 노드마다 인접 노드와 다른 색으로 칠해준다. 

3. 노드마다 인접 노드를 확인해서 같은 색으로 칠한 노드가 있으면 "NO", 없으면 "YES"를 출력한다.

코드

fun main(){
    for(i in 0 until readLine()!!.toInt()){
        var numberOfNode = 0
        var numberOfEdge = 0
        readLine()!!.split(" ").let{
            numberOfNode = it[0].toInt()
            numberOfEdge = it[1].toInt()
        }

        val visit = Array(numberOfNode){false}
        val colors = Array(numberOfNode){-1}
        val graph = Array(numberOfNode){mutableListOf<Int>()}
        // 인접리스트로 그래프 저장
        for(i in 0 until numberOfEdge){
            readLine()!!.split(" ").map{it.toInt()-1}.let{
                graph[it[0]].add(it[1])
                graph[it[1]].add(it[0])
            }
        }

	// DFS로 모든 노드 방문
        (0 until numberOfNode).forEach { node ->
            if (!visit[node]){
                visit[node] = true
                colors[node] = 0	// 첫 노드를 0으로 색칠
                dfs(graph, node, visit, colors)
            }
        }

	// 모든 노드마다 인접 노드가 무슨 색인지 확인한다
        if (isBipartite(graph, colors)){
            println("YES")
            continue
        }
        println("NO")
    }
}

fun isBipartite(graph: Array<MutableList<Int>>, colors: Array<Int>): Boolean{
    graph.indices.forEach { node ->
        graph[node].forEach { adjacent ->
            if (colors[node] == colors[adjacent]){	// 현재 노드와 인접노드의 색이 같으면 false
                return false
            }
        }
    }

    return true
}

fun dfs(graph: Array<MutableList<Int>>, node: Int, visit: Array<Boolean>, colors: Array<Int>){
    graph[node].forEach { toNode ->
        if (!visit[toNode]){
            visit[toNode] = true
            colors[toNode] = (colors[node]+1) % 2	// 인접노드를 현재 노드와 다른 색(0,1)으로 칠한다
            dfs(graph, toNode, visit, colors)
        }
    }
}

리뷰

이분그래프에 대해 알고 있고, DFS와 BFS를 쓸 줄 아는지 묻는 문제였던 것 같다.

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

프로세스

1. 모든 단어는 'a', 'n', 't', 'i', 'c', 다섯 글자를 포함한다.
2. 21개의 글자 중 k-5개를 뽑는 조합을 구한다. (위 다섯 글자는 미리 포함시킨다)
3. 조합마다 읽을 수 있는 단어 수를 구해서 정답과 비교한다. (앞 뒤 공통 글자들은 제외하고 확인)

풀이

알파벳 소문자로 구성된 n개의 단어 중에서, k개의 알파벳만 가지고 만들 수 있는 단어의 최대 개수를 구하는 문제이다.

(1<=n <=50, 0<=k<=26, 8<=단어 길이<=15)

완전 탐색)

여러 풀이 방법이 있는 것 같은데, 나는 모든 k개의 경우의 수를 살펴보는 완전 탐색 방법을 사용했다.

완전 탐색의 연산 횟수를 계산해보자. (1) 26개의 알파벳 중 k개의 경우의 수를 구해서 (2) 각 케이스마다 몇 개의 단어를 만들 수 있는지 확인해야는데, (3) 각 단어마다 어떤 알파벳들로 구성되어 있는지 확인해야 한다. 이를 계산해보면, 최대 연산 횟수는 (26C13) *  50 * 15 = 78억 번으로 1초 만에 통과할 수 없다.

그럼 어떻게 해야 할까?

문제의 조건에 따르면 남극의 모든 단어는 "anta"로 시작해서 "tica"로 끝나므로, 단어를 구성하기 위해선 'a', 'c', 'n', 't', 'i' 5글자는 반드시 포함해야 한다. 그럼 21개의 알파벳 중에서 k-5개의 경우의 수만 구하면 되므로, (21C10) * (15-8)(앞 뒤 네 글자 제외) * 50(단어 수) = 약 1.2억 번의 연산 횟수가 나온다. 나는 1초를 1억 번 정도의 연산으로 알고 있었는데, 요즘 컴퓨터는 1초에 10억 번은 거뜬히 계산한다고 한다. 그러니까 2억 6천 번 정도면 통과 가능한 수치라고 생각할 수 있다! 

이제 지금까지의 과정에 따라 그대로 구현하면 정답을 찾을 수 있다. 나는 조합 함수를 재귀로 구현해서, k-5개의 알파벳 조합을 찾을 때마다 모든 단어를 확인했다. 그리고 그 조합으로 만들 수 있는 단어의 개수를 찾아서 기존의 최대 값과 비교하는 방식으로 구현했다. 

또, n개의 단어를 Set으로 저장해서, 조합을 찾고 단어와 비교할 때 좀 더 빠르게 연산할 수 있도록 했다. 

코드1

import kotlin.math.max

var answer = 0
var n = 0
var k = 0
val alphabets = ('a'.code..'z'.code).filter{ it.toChar() !in "antic" }	// 5개 제외한 알파벳

fun main() {
    readLine()!!.split(" ").let{
        n = it[0].toInt()
        k = it[1].toInt()
    }
    // 5개 미만의 글자로는 어떤 단어로 읽을 수 없다. 
    if (k < 5){
        println(0)
        return
    }

    val words = Array(n){setOf<Char>()}	 // 각 단어의 알파벳 set을 담는 배열
    for (i in 0 until n){
        words[i] = readLine()!!.toSet()
    }

    combine(words, 0, 0, "antic".toMutableList())  // 조합을 찾을 때마다 만들 수 있는 단어 개수 확인
    println(answer)
}

fun combine(words: Array<Set<Char>>, startIdx: Int, combinationCount: Int, combination: MutableList<Char>){
    if (k-5 == combinationCount){	// a,n,t,i,c를 제외하고 k-5개의 글자 조합을 찾으면
        var count = 0
        words.forEach { word ->			// 현재 조합으로 단어를 만들 수 있는지 확인
            if (combination.containsAll(word)){	// '=='으로 확인하면 조합의 글자 수가 더 많은 경우를 놓친다.
                count += 1
            }
        }
        answer = max(answer, count)
        return
    }

    for (i in startIdx until 21){
        combination.add(alphabets[i].toChar())
        combine(words, i+1, combinationCount+1, combination)
        combination.removeAt(5+combinationCount) // 조합에 기본적으로 5개 글자가 들어있음
    }
}

코드2

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.max

val srcLetters = mutableListOf<Char>()
var numOfPick = 0
lateinit var pickedLetters: MutableSet<Char>
lateinit var setsOfWords: Array<MutableSet<Char>>
var answer = 0

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (numOfWords, numOfLetters) = readLine().split(" ").map(String::toInt)

    if (numOfLetters == 26) {
        println(numOfWords)
        return
    } else if (numOfLetters < 5) {
        println(0)
        return
    }

    val fixedLetters = arrayOf('a', 'n', 't', 'i', 'c')
    numOfPick = numOfLetters - 5
    setsOfWords = Array(numOfWords){ HashSet() }
    pickedLetters = HashSet()

    repeat(numOfWords) { setIndex ->
        val word = readLine()
        for (i in 4 until word.length - 4) {
            if (word[i] !in fixedLetters) {
                setsOfWords[setIndex].add(word[i])
            }
        }
    }

    for (ch in 'b'..'z') {
        if (ch !in fixedLetters) {
            srcLetters.add(ch)
        }
    }

    pick(0, 0)

    println(answer)
}

fun pick(count: Int, startIndex: Int) {
    if (count >= numOfPick) {
        val readCount = getHowManyRead()
        answer = max(answer, readCount)
        return
    }

    // 앞으로 뽑아야 할 문자 수 > 남아있는 문자 수
    if (numOfPick - count > 21 - startIndex) {
        return
    }

    for (i in startIndex until 21) {
        pickedLetters.add(srcLetters[i])
        pick(count + 1, i + 1)
        pickedLetters.remove(srcLetters[i])
    }
}

fun getHowManyRead(): Int {
    var count = 0

    for (word in setsOfWords) {
        if (isReadable(word)) count++
    }

    return count
}

fun isReadable(word: Set<Char>): Boolean {
    for (ch in word) {
        if (ch !in pickedLetters) return false
    }

    return true
}

리뷰

• 시간 복잡도 계산하는 게 좀 거부감이 느껴진다. 그렇게 무시하고 풀다가 결국 시간 초과라는 걸 마주하게 된다. 익숙해져야지.
• 무시할 수 있는 문제 조건 같은 건 없다. 예를 들면 antic이라던지, antic이라던지..ㅠㅠ

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

풀이

N명의 학생이 최대 M개의 블록을 갖고 있으며, 각자가 갖는 블록들의 높이는 모두 다르다. 이 때, 학생 당 최대 하나의 블록을 사용해서 높이가 H인 블록을 쌓는 방법은 몇 가지가 있을지 찾는 문제이다.

1) 완전 탐색

먼저 모든 경우의 수를 계산하는 완전 탐색을 생각해볼 수 있다. 하지만 시간 복잡도가 n x n x n ... x n = O(n^m)인 지수 시간 복잡도가 나오므로 모든 경우의 수를 고려하는 방법은 불가능하다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 10)

2) 다이나믹 프로그래밍

어떻게 풀 수 있을까? 모든 경우의 수를 따져야할 것 같은데 시간이 비정상적으로 길어진다. 이 때 다이나믹 프로그래밍을 생각해볼 수 있는 것 같다. (느낌적인 느낌)

점화식을 어떻게 세울 수 있을까? 이 문제는 배낭문제와 유사한데, 블록을 쌓는 모든 방법을 2가지 경우의 수로 나눠서 생각해볼 수 있다. (1)임의의 [i]번째 학생의 블록을 사용하지 않고 블록을 쌓는 방법과 (2)[i]의 블록을 반드시 사용해서 블록을 쌓는 방법. 이것을 점화식으로 연결해서 생각해보면 다음과 같은 점화식이 나온다.

DP[i][0] = 1
DP[i][h] = DP[i-1][h]   , if ( h < h[i] )
DP[i][h] = (1)DP[i-1][h] + (2)DP[i-1][ h - h[i] ]    (h[i]: i번째 학생의 블록의 높이)

DP[i][h]는 i번째 학생까지 확인했을 때, 높이 h인 블록을 쌓는 경우의 수를 의미한다.

식 (2)는 [i]번째 학생의 블록을 반드시 사용하는 경우인데, 이는 높이 h에서 [i]가 사용한 블록의 높이를 뺀 높이의 블록을 [1~(i-1)] 번째 학생들의 블록만으로 쌓는 경우의 수와 같다.

사실 학생들마다 여러 블록을 가지고 있기 때문에, 식을 좀 더 정확히 표현하면

DP[i][h] = (1)DP[i-1][h] + (2)sum(DP[i-1][ h - h[i] ])이 된다.

DP[i][0] = 1인 이유는, 학생[i]의 블록을 반드시 사용할 때 h - h[i] = 0이라면 그 블록 하나만으로 쌓는 경우의 수 한 가지를 고려해줘야 하기 때문이다. 1로 초기화하지 않으면 dp를 진행해도 모든 값이 0으로 나온다. 

이를 따라서 백준의 예시 입력을 dp 테이블로 작성하면 다음과 같다.

우리가 원하는 정답은 DP[n][h]인데, 이를 알기 위해서는 i=0, h=1일 때의 값부터 알아야 한다. 재귀함수와 메모이제이션 기법을 사용할 수 있지만, 나는 바텀업 방식을 사용했다.

위 점화식을 코드로 나타내면 아래와 같다.

// dp(점화식) 진행
for (i in 1..n){
    for (h in 1..height){
       var sum = 0
       
       // 학생들이 여러개의 블록을 갖고 있으므로 각 블록마다 식을 적용해서 합을 구한다.
       // sum(DP[i-1][ h - h[i] ])
        blocks[i].forEach { eachBlock ->
            if (h >= eachBlockt){
                sum += dp[i-1][h - eachBlock]
                sum %= 10007
            }
        }
        
        dp[i][h] = dp[i-1][h] + sum	// DP[i][h] = (1)DP[i-1][h] + (2)sum(DP[i-1][ h - h[i] ]) 
        dp[i][h] %= 10007
    }
}

코드

fun main() {
    var n = 0
    var maxBlock = 0
    var height = 0

    readLine()!!.split(" ").also {
        n = it[0].toInt()
        maxBlock = it[1].toInt()
        height = it[2].toInt()
    }

    val blocks = Array(n+1){ mutableListOf<Int>() }		// 각 학생들의 블록 배열
    val dp = Array(n+1){ Array(height+1){0} }		// dp 테이블

    // 학생들의 블록 입력 받아서 추가
    for (i in 1..n){
        dp[i-1][0] = 1
        readLine()!!.split(" ").forEach {
            blocks[i].add(it.toInt())
        }
    }

    // dp(점화식) 진행
    for (i in 1..n){
        for (h in 1..height){
            var sum = 0
            
           // 학생들이 여러개의 블록을 갖고 있으므로 각 블록마다 식을 적용해서 합을 구한다.
           // sum(DP[i-1][ h - h[i] ])
            blocks[i].forEach { eachBlock ->
                if (h >= eachBlockt){
                    sum += dp[i-1][h - eachBlock]
                    sum %= 10007
                }
            }
            
            dp[i][h] = dp[i-1][h] + sum	// DP[i][h] = (1)DP[i-1][h] + (2)sum(DP[i-1][ h - h[i] ]) 
            dp[i][h] %= 10007
        }
    }

    println(dp[n][height])
}

리뷰

• 10007로 나누는 거 처음에 까먹고 틀렸다..ㅋ
• 내 머리론 dp가 직관적으로 이해가 쉽진 않다. 가장 이해하기 어려웠던 건 i번째 학생을 고려할 때 왜 특정 학생으로 계산을 하느냐는 것이었다. 어떤 학생이든 될 수 있는데 왜 특정 학생으로 계산을 하는건지 이해가 안됐는데, 지금껏 이해한 바로는 "결국 n번째까지 가면서 모든 학생을 고려하기 때문에 순서는 상관 없다" 이다. 맞나?ㅋㅋ
• dp가 재귀와 관련돼서인지 이해하기가 어렵다. 이전 항과의 관계를 중심으로 논리적으로 이해하는 게 정신 건강에 좋을듯 하다!

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

문제

욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다.

이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다.

1초 동안 욱제의 캐릭터가 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다.

욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지 구해보자.

입력

8개 줄에 걸쳐서 체스판의 상태가 주어진다. '.'은 빈 칸, '#'는 벽이다. 가장 왼쪽 아랫칸은 항상 벽이 아니다.

출력

욱제의 캐릭터가 가장 오른쪽 윗 칸에 도착할 수 있으면 1, 없으면 0을 출력한다.

풀이

BFS로 풀 수 있는 그래프 문제인데, 특징은 벽이 아래로 움직인다는 것이다. 벽과 캐릭터가 충돌하면 캐릭터는 더이상 움직일 수 없고, 캐릭터는 인접 방향, 대각선 방향으로 움직이거나 제자리에 있을 수도 있다.

큐에 있는 모든 캐릭터를 BFS에 따라 모든 방향으로 한 칸씩만 움직인다. 제자리에 있는 것도 가능하다는 것이다. 난 이걸 빼먹어서 틀렸다..ㅋ. 주의할 점은 벽의 위치에 따라 상황이 달라지므로 중복 방문은 체크하면 안되는데, 같은 턴 내에서는 체크를 해도 된다.

한 칸의 BFS 순회가 끝나면 벽을 움직여서 상황에 맞게 캐릭터와 벽을 소멸시킨다. 그리고 이 과정을 반복해서 BFS 전체 프로세스가 끝나기 전에 목표에 도달하면 1을, 그러지 못하면 0을 반환한다.

좌표(Point)를 data class로 만들어서 캐릭터와 캐릭터의 움직임(dPoint)을 표현했으며, ArrayDeque을 사용해서 큐를 구현했다.

그리고 벽은 움직이거나 소멸시키기 위해 리스트에 따로 저장해서 관리했고, Pair를 사용해서 좌표로 표현했다.

코드

fun main(){
    data class Point(var x: Int, var y: Int)

    var wallList = mutableListOf<Pair<Int, Int>>()
    val queue = ArrayDeque<Point>()
    val dPoint = arrayListOf(Point(0, 0),
        Point(0, -1), Point(1, -1), Point(1, 0), Point(1, 1), Point(0, 1), Point(-1, 1), Point(-1, 0), Point(-1, -1)
    )

    repeat(8) { i ->
        readLine()!!.forEachIndexed { j, ch ->
            if (ch == '#') wallList.add(Pair(j, i))
        }
    }

    queue.add(Point(0, 7))

    while (queue.isNotEmpty()) {
        val queueSize = queue.size

        repeat(queueSize) { _ ->
            val character = queue.removeFirst()

            for (d in dPoint) {
                val newPoint = Point(character.x + d.x, character.y + d.y).also {
                    if (it.x == 7 && it.y == 0) {
                        println(1)
                        return
                    }
                }

                if (newPoint.x in 0..7 && newPoint.y in 0..7 && Pair(newPoint.x, newPoint.y) !in wallList) {
                    queue.add(newPoint)
                }
            }
        }

        val removingList = mutableListOf<Point>()
        wallList = wallList
            .asSequence()
            .filter{ it.second+1 < 8 }
            .map{
                for(character in queue){
                    if (it.first == character.x && it.second+1 == character.y){ removingList.add(character) }
                }
                Pair(it.first, it.second + 1)}
            .toMutableList()

        removingList.forEach { queue.remove(it) }
    }
    println(0)
}

리뷰

코틀린으로 백준 형식의 문제와 그래프 문제를 처음 풀어봤는데, 어색했고 파이썬으로 풀 때보다 어려웠다. 

코드가 객체로도 좌표를 표현하고, Pair로도 좌표를 나타내고 있어서 비효율에 중구난방이 됐다.

곰곰이 생각해보니까 좌표를 사용하는데, 그래프는 사용하지 않는 것에서부터 뒤죽박죽이 됐다. 그래서 벽이랑 캐릭터 충돌을 확인할 때마다 반복문을 돌리고 있다. 정리가 더 필요하다.