백준 2469 사다리 타기 Kotlin (구현)

문제 출처 : https://www.acmicpc.net/problem/2469

2469번: 사다리 타기

문제

k명의 참가자들이 사다리 타기를 통하여 어떤 순서를 결정한다. 참가자들은 알파벳 대문자 첫 k개로 표현되며, 사다리 타기를 시작할 때의 순서는 아래 그림과 같이 항상 알파벳 순서대로이다. 

k=10 인 예를 들어 보자. 10명의 A, B, C, D, E, F, G, H, I, J 참가자들이 사다리 타기를 준비한다. 아래 그림은 10개의 세로 줄과 5개의 가로 줄을 가지고 있는 사다리의 한 예를 보여주고 있다.  

이 사다리에서 점선은 가로 막대가 없음을, 굵은 가로 실선은 옆으로 건너갈 수 있는 가로 막대가 있음을 나타내고 있다.  

따라서 위에 제시된 사다리를 타면 그 최종 도달된 순서는 왼쪽으로부터 A, C, G, B, E, D, J, F, I, H 가 된다. 

사다리 타기는 세로 막대를 타고 내려오는 중에 가로막대를 만나면 그 쪽으로 옮겨 가면서 끝까지 내려가는 과정이다.  따라서 사다리 타기의 규칙 특성상 아래 그림과 같이 두 가로 막대가 직접 연결될 수는 없으므로 이 상황은 이 문제에서 고려할 필요가 없다.

우리는 하나의 가로 줄이 감추어진 사다리를 받아서 그 줄의 각 칸에 가로 막대를 적절히 넣어서 참가자들의 최종 순서가 원하는 순서대로 나오도록 만들려고 한다.  

입력에서 사다리의 전체 모양은 각 줄에 있는 가로 막대의 유무로 표현된다. 각 줄에서 가로 막대가 없는 경우에는 ‘*’(별)문자, 있을 경우에는 ‘-’(빼기) 문자로 표시된다. 그리고 감추어진 특정 가로 줄은 길이 k-1인 ‘?’ (물음표) 문자열로 표시되어 있다.   

입력

첫 줄에는 참가한 사람의 수 k가 나온다(3 ≤ k ≤ 26). 그 다음 줄에는 가로 막대가 놓일 전체 가로 줄의 수를 나타내는 n이 나온다(3 ≤ n ≤ 1,000). 그리고 세 번째 줄에는 사다리를 타고 난 후 결정된 참가자들의 최종 순서가 길이 k인 대문자 문자열로 들어온다.  

k와 n, 그리고 도착순서 문자열이 나타난 다음, 이어지는 n개의 줄에는 앞서 설명한 바와 같이 ‘*’와 ‘-’ 문자로 이루어진 길이 k-1인 문자열이 주어진다. 그 중 감추어진 가로 줄은 길이가 k-1인 ‘?’ 문자열로 표시되어 있다.

출력

입력 파일 세 번째 줄에서 지정한 도착순서가 해당 사다리에서 만들어질 수 있도록 감추어진 가로 줄을 구성해야 한다. 

여러분은 감추어진 가로 줄의 상태를 재구성하여 이를 ‘*’(별) 문자와 ‘-’(빼기) 문자로 구성된 길이 k-1인 문자열로 만들어 출력하면 된다.

그런데 어떤 경우에는 그 감추어진 가로 줄을 어떻게 구성해도 원하는 순서를 얻을 수 없는 경우도 있다.  이 경우에는  ‘x’(소문자 엑스)로 구성된 길이 k-1인 문자열을 출력해야 한다.

알고리즘 분류

• 구현
• 문자열

풀이

본인은 이러한 그래프와 그래프 경계선을 이용하는 문제에 약하다.

하지만 이 문제는 인덱스를 어떻게 다룰지 고민하지 않아도 되는 문제이다.

가장 고민했던 부분은 B에서 출발한다고 했을 때, 그림으로 나타난 가로 선을 만났는지 어떻게 판단할지 설계하는 것이었는데,

그냥 ABCDEFGHIJ와 사다리의 인덱스(열)를 똑같이 둔 다음 어떠한 행에서 해당 열에 '-'가 있다면 swap만 해주면 된다.

위의 그림에서 ABC부분을 보자.

0	1	2	3	4	5	6	7	8	9
A	B	C	D	E	F	G	H	I	J

0	1	2	3	4	5	6	7	8
*	-	*	*	*	-	*	*	*

0	1	2	3	4	5	6	7	8
-	*	-	*	*	*	*	*	*

첫 번째 행을 만났을 때 B와 같은 열에 -가 있다.

B와 C를 swap 한다. Result :ACB

두 번째 행을 만났을 때 A와 같은 열에 -가 있으므로 A와 C를 swap한다. Result : CAB

B와 같은 열에 -가 있으므로 B와D를 swap한다. Result : CADB

위와 같이 굳이 각 시작점 별로 사다리를 타는 것 보다, 그냥 한 행씩 비교하여 swap해 주면 된다.

 

위와 같은 방법으로 사다리의 처음 상태 Before(ABCDEFGHI)를 ?가 있는 행까지 내리고, 사다리의 결과인 After(ACGBEDJFIH)를 ?가 있는 행까지 올린다.

이후 Before와 After를 비교하여 문자가 다르다면 swap하고 -을 붙이고, 같다면 그냥 *을 붙인다.

이렇게 ?에서 추가로 한 번 더 swap한 결과 Before과 After가 같다면 우리가 ???를 *,-로 바꾼 답을 출력하면 되고, 다르다면 xxxxxxx를 출력한다.

 

코드

import java.util.*
val br = System.`in`.bufferedReader()

fun getInt() = br.readLine().toInt()

lateinit var graph: Array<String>
var lineNum = -1

fun swap(c: Int, sb: StringBuilder){
    sb[c] = sb[c+1].also { sb[c+1] = sb[c] }
}

fun main() = with(System.out.bufferedWriter()){
    //input
    val k = getInt()
    val n = getInt()
    var before = StringBuilder()
    for(i in 0 until k){
        before.append('A'+i)
    }
    var after = StringBuilder(br.readLine())
    graph = Array(n){
        val line = br.readLine().apply{
            if(contains('?')){
                lineNum = it
            }
        }
        line
    }
    //solve
    //위에서부터 ?까지 순서 변경
    for(r in 0 until lineNum){
        for(c in 0 until k-1){
            if(graph[r][c]=='-'){
                swap(c,before)
            }
        }
    }
    //아래서부터 ?까지 순서 변경
    for(r in n-1 downTo lineNum){
        for(c in 0 until k-1){
            if(graph[r][c]=='-'){
                swap(c,after)
            }
        }
    }
    //before after비교하여 다른 문자가 있으면 swap, -추가, 같으면 *추가
    val result = StringBuilder()
    for(i in 0 until k-1){
        if(before[i] != after[i]){
            swap(i,before)
            result.append('-')
        }
        else{
            result.append('*')
        }
    }
    //output
    //값이 같으면 result 출력, 다르면 *****
    if(before.toString() == after.toString())
        write("$result")
    else{
        for(i in 0 until k-1){
            write("x")
        }
    }

    close()
}