사다리 타기

작성일 | In

[백준] 2468번 - 사다리 타기

문제 링크

KOI 2010 초등부 문제.
주어진 사다리에서 가로 한 줄을 완성하여 주어진 알파벳 순서를 완성할 수 있는지 묻는 문제이다.
물음표로 주어지는 가로 직전까지의 알파벳 순서와, 직후의 알파벳 순서를 구해 비교하면 된다.
필자는 사다리를 입력 받으면서 순서를 같이 계산해나가는 코드를 짜서 afterBlank, result 배열이 필요했지만, 사다리를 전부 입력받은 뒤 주어진 목표 알파벳 순서에서 사다리를 역으로 타 가면서 물음표 직후까지 순서를 계산해나가면 메모리를 좀 더 적게 사용할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using namespace std;

/*
    start       : 처음 알파벳 순서 (abc순)
    target      : 마지막 사다리 이후 알파벳 순서. 입력으로 주어짐.
    aftreBlank  : 물음표 사다리 직후 알파벳 순서가 마지막 사다리까지 어떻게 변화하는지 체크
    result      : 물음표 사다리 직후 알파벳 순서.
*/

vector<char> start;
vector<char> target;
vector<char> afterBlank;
vector<char> result;
char answer[26];
int k,n;

void swapElement(int a, int b, vector<char>& vec) {
    vec[a]^=vec[b]; vec[b]^=vec[a]; vec[a]^=vec[b];
}

int main(void) {
    scanf("%d %d", &k, &n);

    target.resize(k);
    start.resize(k);
    for(int i=0; i<k; ++i) {
        scanf(" %c", &target[i]);
        start[i] = i+'A';
    }

    // 물음표 직후 알파벳 배열은 알 수 없으나, 물음표 직후 알파벳 순서가 
    // 마지막까지 사다리를 탄 뒤에 어떻게 변할지는 계산해둘 수 있다.
    // 따라서 afterBlank에 0~k-1 수를 넣어두고, 사다리타기가 끝난 후의 
    // afterBlank와 target을 통해 물음표 직후 알파벳 순서를
    // 알아낼 수 있다.
    afterBlank.resize(k);
    for(int i=0; i<k; ++i)
        afterBlank[i] = '0'+i;
    
    int isAfterBlank = 0;
    for(int i=0; i<n; ++i) {
        for(int j=0; j<k-1; ++j) {
            char c;
            scanf(" %c", &c);
            if(c == '*') continue;
            else if(c == '-') {
                if(!isAfterBlank)
                    swapElement(j,j+1,start);
                else
                    swapElement(j,j+1,afterBlank);
            }
            else
                isAfterBlank = true;
        }
    }

    result.resize(k);
    for(int i=0; i<k; ++i)
        result[afterBlank[i]-'0'] = target[i];
    
    memset(answer, '*', k-1);
    for(int i=0; i<k-1; ++i) {
        if(start[i] != result[i]) {
            if(start[i+1] == result[i] && start[i] == result[i+1]) {
                answer[i] = '-';
                swapElement(i,i+1,start);
            }
            else {
                for(int i=0; i<k-1; ++i)
                    printf("x");
                exit(0);
            }
        }
    }
    for(int i=0; i<k-1; ++i)
        printf("%c", answer[i]);
}
0%