[C++] 백준 2469 : 사다리 타기

문제

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

 

 

풀이

? 줄을 기준으로 위에서 아래로 사다리를 타고 내려왔을 때 결과 배열(=up 배열)과 ?줄을 기준으로 아래에서 위로 사다리를 타고 올라갔을 때의 결과 배열(=down 배열)을 구한 후, 두 배열을 비교하여 up 배열을 down 배열과 같게 만들 수 있는지를 확인한다.

 

 구체적인 구현 방식은 아래의 코드 주석을 참고하면 될 것 같다. 

 

코드

#include <iostream>
using namespace std;

int k,n;
string str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string result;
int flag = 0;

int main()
{
    cin >> k >> n >> result;
    string s[n] = {};
    for(int i=0; i<n; i++){
        cin >> s[i];
        
        // 아직 모르는 가로줄의 위치를 구함.
        if(s[i][0] == '?'){
            flag = i;
        }
    }
    
    // 위에서 ? 전까지 위치를 구함. 
    char up[k] = {};
    for(int i=0; i<k; i++){
        int row = i;
        int n_row=i;
        for(int j=0; j<flag; j++){
            
            // 현재 row를 기준으로 좌우 사다리를 확인(좌우 확인이 가능한 경우)
            if(row >0 && row<k-1){
                // 왼쪽 사다리 검사
                if(s[j][row-1] == '-'){
                    row--;
                }
                
                // 오른쪽 사다리 검사 
                else if(s[j][row] == '-'){
                    row++;
                }
            }
            
            // 오른쪽만 확인할 수 있는 경우
            else if(row == 0){
                // 오른쪽 사다리 검사 
                if(s[j][row] == '-'){
                    row++;
                }
            }
            
            // 왼쪽만 확인할 수 있는 경우 
            else if(row==k-1){
                // 왼쪽 사다리 검사
                if(s[j][row-1] == '-'){
                    row--;
                }
            }
        }
        
        up[row] = str[i];
    }

    char down[k] = {};
    // 아래에서 ? 전까지 위치를 구함
    for(int i=0; i<k; i++){
        int row = i;
        for(int j=n-1; j>flag; j--){
            // 현재 row를 기준으로 좌우 사다리를 확인(좌우 확인이 가능한 경우)
            if(row >0 && row<k-1){
                // 왼쪽 사다리 검사
                if(s[j][row-1] == '-'){
                    row--;
                }
                
                // 오른쪽 사다리 검사 
                else if(s[j][row] == '-'){
                    row++;
                }
            }
            
            // 오른쪽만 확인할 수 있는 경우
            else if(row == 0){
                // 오른쪽 사다리 검사 
                if(s[j][row] == '-'){
                    row++;
                }
            }
            
            // 왼쪽만 확인할 수 있는 경우 
            else if(row==k-1){
                // 왼쪽 사다리 검사
                if(s[j][row-1] == '-'){
                    row--;
                }
            }
        }
        
        down[row] = result[i];
    }

    string failed_ans = "";
    // 불가능할 때 반환할 문자열 
    for(int i=0; i<k-1; i++){
        failed_ans= failed_ans+'x';
    }
    
    string ans="";
    // up과 down 배열의 차이를 이용해 필요한 사다리 계산
    for(int i=0; i<k; i++){
        // 추가적인 사다리가 필요한 경우 : up과 down이 다른 경우
        if(up[i] != down[i]){
            // 사다리를 놓아 원하는 위치로 이동 가능한 경우 
            if(up[i] == down[i+1] && up[i+1] == down[i]){
                ans= ans+'-' + '*';
                i++;
            }
            
            // 불가능한 경우 : 사다리 1개보다 더 많은 사다리가 필요한 경우
            else{
                cout << failed_ans << "\n";
                return 0;
            }
        }
        // 추가적인 사다리가 필요 없는 경우 
        else{
            ans=ans+'*';
        }
    }
    
    // 결과 출력 
    for(int i=0; i<k-1; i++){
        cout << ans[i];
    }
   
    return 0;
}