[백준 2469] - 사다리타기(C++) [골드5]

📕문제

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인 문자열을 출력해야 한다.

 

🔎문제해석

• 문제를 이해하는데 꽤 시간이 많이 걸렸다.
• 우선 의도적으로 감추어진 가로줄을 찾아야한다.
  • 처음에는 그냥 디폴트로 3번째 줄인줄 알고 코드를 작성했는데, 계속 틀리길래 혹시나 해서 찾아주는 코드를 넣었더니 통과했다.. ㅡ,ㅡ 출력에는 세번째 줄이라면서요!
• 문제를 푸는 방식은 꽤 다양할 것 같다.
  • 초기에는 그냥 bfs식으로 풀다가 막혀서 그냥 구현으로 해결했다.

💻문제 풀이

• 우선 출발하는 알파벳을 k개 까지 할당해서 모두 start라는 배열에 int형으로 넣어줬다.
  • 아스키코드 값을 이용해서 'A'+i하면 착착 들어가게 된다.
• 그리고 입력받은 도착 알파벳을 모두 finish라는 배열에 int형으로 넣어줬다.
  • 이것도 str[i]를 해주면 된다. 
• Int형으로 바꿔주는 이유는 비교하기 편해서이다. [문자열 함수를 이용하면 굳이 int로 안바꿔도된다.]
• 그 다음 입력받은 행렬에서 ?가 나온다면 그때의 열을 우리는 감추어진 열이라고 처리한다.
  • 이 작업 반드시 해야함.
• 그 다음 start와 finish를 ?가 나오는 열 전까지 사다리를 진행한다.
  • 진행하는 방식
    • 해당 좌표에 문자가 *이라면 그냥 진행
    • 해당 좌표에 문자가 -이라면 서로의 알파벳을 바꿔준다. 
      • swap(start[j],start[j+1]) 요론식
  • finish도 동일하다.
  • 그 배열의 진행하는 방식은 똑같지만, start배열은 0에서부터 감추어진열 전까지
    finish 배열은 n-1부터 감추어진열+1까지 진행한다.
• 그럼 이제 start와 finish 모두 감추어진 열 까지 진행을 완료한 상태다.
  • 아래 그림을 보면 파란색으로 칠해진 부분이 가려진 가로열이고, 
    그 위의 파란글씨는 start 배열, 빨간 글씨는 finish 배열이다.

• 여기서 start와 finish가 같다면 그대로 진행해도 된다는 뜻이기에 *을 기록한다.
• 만약 start와 finish가 다르다면
  • BD 와 DB 가 예가 될 것이다. 즉 start [i]와 finish [i+1]이 같아야 하고, start [i+1]과 finish [i]가 같아야 함.
  • 이 경우를 안 해준다면 CB와 BD 같은 경우도 된다는 결과물이기 때문이다. 
  • 즉 서로 교차하는 알파벳이어야 한다. 
    • 하지만 이 경우 -가 기록된다면 충분히 가능한 결과이기에 -을 기록해 준다.
    • 그다음 -를 기록했기에, start 배열에서 B와 D를 바꿔준다.
• 만약 위의 경우의 수에 모두 걸리지 않는다면 그때는 결과물을 도출할 수 없기에 x를 k-1개 출력한다.

👨🏽‍💻코드

코드에 대한 세부 설명은 주석으로 처리해 놨습니다. 이해가 안 되신다면 댓글 부탁@@

/*
백준 2469 사다리타기 골드5
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int k, n;
string str;
vector<int> start;
vector<int> finish;
vector<vector<char>> graph;
vector<char> result;
int fault = 0;
int main()
{
    cin >> k >> n;
    start.resize(k, 0);
    finish.resize(k, 0);
    graph.resize(n, vector<char>(k, 0));
    cin >> str;
    for (int i = 0; i < k; i++) // 알파벳을 int형으로 바꾸기
    {
        start[i] = 'A' + i;
        finish[i] = str[i];
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < k - 1; j++)
        {
            cin >> graph[i][j];
            if (graph[i][j] == '?') // 가려진 열 찾기
            {
                fault = i;
            }
        }
    }
    for (int i = 0; i < fault; i++) // start 배열을 ?가 만나기전 까지 진행
    {
        for (int j = 0; j < k - 1; j++)
        {
            if (graph[i][j] == '-')
            {
                swap(start[j], start[j + 1]);
            }
        }
    }
    for (int i = n - 1; i >= fault + 1; i--) // finish 배열을 ?가 만나기전 까지 진행
    {
        for (int j = 0; j < k - 1; j++)
        {
            if (graph[i][j] == '-')
            {
                swap(finish[j], finish[j + 1]);
            }
        }
    }
    for (int i = 0; i < k - 1; i++)
    {
        if (start[i] == finish[i]) // 두 배열이 같다면 그대로 진행
        {
            result.push_back('*');
        }
        else if (start[i] == finish[i + 1] && start[i + 1] == finish[i]) // 두 배열이 다르지만 교차하는 상태라면 -을 기록, swap해준다.
        {
            swap(start[i], start[i + 1]);
            result.push_back('-');
        }
        else // 만약 위 경우의 수에 걸리지 않는다면 결과물을 도출할 수 없기에 x를 k-1개 기록한다.
        {
            result.assign(0, 0);
            for (int j = 0; j < k - 1; j++)
            {
                result.push_back('x');
            }
        }
    }
    for (int i = 0; i < k - 1; i++) // 결과 출력
    {
        cout << result[i];
    }
}

✔느낀 점

• 종강을 하고 거의 한 달 반 만에 알고리즘을 풀었는데 확실히 쉬었다 하니 많이 녹슬고, 머리가 굳은 거 같습니다.
• 문제 자체는 정말 재미있고, 난이도도 적당했습니다
• 처음에 백트래킹, bfs를 사용하여 풀려고 했지만, 신경 써줘야 할 요소가 많았기에, 구현으로 풀었습니다.