문제

문제 링크

삼성 문제고 구현 문제다.

다음과 같이 사다리가 주어질때 i번째 최종적으로 i번째에 도착할 수 있도록 사다리를 추가하는 문제다.

역시나 범위도 깔끔하지 못해서 잘 정해줘야한다.

사다리를 그래프로 보면 dfs로 빈칸에 사다리를 추가해주면서 종료조건인지 체크해주면 된다.

그래프 크기를 HxN이라고하면 시간 복잡도는 HxN에 종료조건을 체크하는 함수가 그래프를 돌며 swap해줘야해서 HxNx3에 시간복잡도를 갖는다. 총 (HxN)^2인데 다행히 H와 N이 각각 30,10이 최대여서 300^2=9만해서 상수x9만 정도로 낮은 시간복잡도를 갖는다.

삽질

해당 문제는 풀다가 반복되는 틀렸습니다와 시간초과를 마주쳤다. 시간 복잡도를 가장 먼저 계산해봤는데 넉넉했고 시간 측정에서도 별 문제가 없었다. 로직도 원하는 결과대로 나왔고 최대 크기일때나 예외인 경우도 체크해줬다.

멘탈이 나갈거같아서 다음날 다른 방식으로 알고리즘을 작성하니 런타임에러가 떴다.

아..

사실상 void 함수에 bool 타입으로 함수를 만들어주고 반환값을 안넣어줘서 생긴 문제였다.

괜히 시간초과와 틀렸습니다에 눈이 멀어 이상한 짓을 계속해서 했던거같다.

다행히 반환값만 맞춰주니 어떤 알고리즘을 써도 정답을 받을 수 있었다.

code

/**
 * 백준 15684
 * 시뮬레이션
*/
#include <bits/stdc++.h>

using namespace std;

int M,N,H;
int graph[31][11]={0}; // H*N-1
int ladderArr[11];

void swap(int *arr,int a,int b);
bool addCheck(int y,int x);
void addLadderDetail(int y,int x,int cnt,int limit);
void addLadder(int num);
bool check();

void swap(int *arr,int a,int b){
    int tmp=arr[a];
    arr[a]=arr[b];
    arr[b]=tmp;
}
bool addCheck(int y,int x){
    if(graph[y][x]==1) return false;
    if((x-1>=0)&&graph[y][x-1]==1) return false;
    if((x+1<=N-1)&&graph[y][x+1]==1) return false;
    return true;
}
void addLadderDetail(int y,int x,int cnt,int limit){
    // 마지막
    if(cnt>=limit){
        if(check()){
            cout<<limit<<endl;
            exit(0);
        }
        return;
    }

    // 다음 사다리 추가
    for(int i=y;i<=H;i++){
        for(int j=1;j<=N-1;j++){
            if(i<=y && j<=x) continue;
            if(addCheck(i,j)){
                graph[i][j]=1;
                addLadderDetail(i,j,cnt+1,limit);
                graph[i][j]=0;
            }
        }
    }
}
void addLadder(int num){
    // num 개 사다리 추가
    for(int i=1;i<=H;i++){
        for(int j=1;j<=N-1;j++){
            if(addCheck(i,j)){
                graph[i][j]=1;
                addLadderDetail(i,j,1,num);
                graph[i][j]=0;
            }           
        }
    }
}
bool check(){
    for(int i=1;i<=N;i++) ladderArr[i]=i;
    
    // swap
    for(int i=1;i<=H;i++){
        for(int j=1;j<=N-1;j++){
            if (graph[i][j]==1) swap(ladderArr,j,j+1);
        }
    }
    
    // 순서에 맞는지 확인
    for(int i=1;i<=N;i++){
        if(ladderArr[i]!=i) return false;
    }

    return true;
}
void distCheck(){
    for(int i=1;i<=N;i++) ladderArr[i]=i;

    // swap
    for(int i=1;i<=H;i++){
        for(int j=1;j<=N-1;j++){
            if (graph[i][j]==1) swap(ladderArr,j,j+1);
        }
    }

    int maxDist=0;
    for(int i=1;i<=N;i++){
        int dist=abs(ladderArr[i]-i);
        maxDist=(dist>maxDist)?dist:maxDist;
    }
    
    if(maxDist>3){
        cout<<-1<<endl;
        exit(0);
    }
}
int main(void){
    cin>>N>>M>>H; // 세로,가로,가로선 수
    for(int i=0;i<M;i++){
        int a,b;
        scanf("%d %d",&a,&b);
        // a 가로선에 b,b+1 세로선
        graph[a][b]=1;
    }
    // 최대 거리가 3을 넘는지
    distCheck();

    // 0일때 따로 처리
    if(check() || M==0){
        cout<<0<<endl;
        exit(0);
    }

    // 사다리추가하며 순서 맞는지 체크
    for(int num=1;num<=3;num++){
        addLadder(num);
    }
    cout<<-1<<endl;
    return 0;
}