백준 15684 사다리 조작 c++ [컴공과고씨]

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

15684번: 사다리 조작

 

이 문제는 DFS와 백트래킹을 사용하는 문제입니다.

 

문제 정리

사다리 타기를 하는데 1번 위치가 사다리를 타면 1번 위치로 내려가고 2번은 2번 위치, 즉, i번이 사다리를 탔을 때 결과가 i번이도록 사다리에 가로선을 추가하는 것입니다.

가로선은 최대 3까지 가능하며 가로선을 최소로 하는 사다리를 만드는 것입니다.

 

문제 해결 방법

사다리 표시 방법 부터 정해야 합니다. 배열로 정의를 할 것이고 저는 ladder_pos[y][x]로 정의 했습니다.

 y는 가로선의 번호, x는 세로선의 번호를 뜻합니다. (저는 y는 0부터 시작하고 x는 1부터 시작하도록 코드를 짰습니다.)

ladder_pos[0][1] = true 라는 것은 

 

ladder_pos[0][1]

이런식으로 높이 0번째에 1번에서 2번을 이어주는 가로선이 있다는 뜻입니다.

정리하면 ladder_pos[y][x] => 높이 y번째에 x번 에서 x+1번째를 이어주는 가로선이다.

 

먼저 우리는 가로선을 최소로 할 것이기 때문에 나누어서 생각해야합니다.

가로선을 추가 하지 않을 때, 1개 추가할 때, 2개 추가할 때 3개 추가할 때로 나누어 생각합니다.

 

이제 dfs를 사용할 것인데 먼저 가로선의 추가 개수 여부를 체크하여서 가로선을 추가해야할 경우와 그렇지 않은 경우로 나누어 줍니다.

만약 가로선을 더 이상 추가하지 않아도 된다면 사다리가 정상인지 확인해주어야 합니다.

확인하는 방법은 세로선 시작 위치를 verti 변수에 저장해 줍니다. 그 후 내려갈 건데 내려갈 때 마다 위치를 확인하여 가로선이 그어져 있는지 확인합니다. 위 그림 경우에서 ladder_pos[0][1] = true 이므로 verti 에 +1를 해주면 됩니다.

즉, ladder_pos[현재 높이][현재 verti]가 true이면 오른쪽으로 이동합니다. 

만약 verti > 1 이고 ladder_pos[현재 높이][현재 verti - 1]이 true라면 왼쪽으로 이동합니다. 이것은 위 그림에서 만약 처음 위치가 2번이라고 생각하면 됩니다. 그럼 verti가 2가 되고 현재 높이는 0 이기 때문에 ladder_pos[0][2-1] = true 이므로 사다리를 타면 왼쪽으로 가게 됩니다.

 

이렇게 해서 하나의 세로선에 대해 모든 높이에 대해서 했을 때 verti의 결과가 처음 위치와 같으면 이 세로선은 가능하므로 다음 세로선을 확인하면 됩니다. 만약 다르다면 이 사다리는 잘못된 사다리 이므로 bool 변수에 표시를 하고 다음 세로선을 확인하지 않습니다. 

그 다음 다른 가로선을 추가해 다른 사다리의 경우를 확인해 줍니다.

만약 모든 세로선이 정상이라면 답이기 때문에 flag에 true를 해줍니다. 그 후  ladder_cnt를 출력해주면됩니다.

 

가로선을 추가하는 방법

모든 가로선을 추가할 수 있는 경우의 수를 따져줄 것인데 이때 만약 가로선을 2개 추가하는 예를 들면 먼저 하나를 추가한 것을 고정해 놓고 다음 부분을 추가 하고 다음 추가하고 확인하고 이런식으로 갑니다. 또한 사다리를 추가할 때 문제 조건에서 곂치거나 점을 공유 하면 안됩니다. 그러므로 추가 하려는 점 양 쪽으로 사다리가 있는지 확인후에 없으면 추가합니다.

이렇게 사다리를 추가한 후 백트래킹을 이용해서 dfs에 넣는데 이 때 가로선 위치 추가한 y좌표와 가로선 추가를 했기 때문에 가로선 추가 카운트를 해줍니다. 가로선 위치 추가한 y좌표를 넣는 이유는 앞에서 이미 사다리를 추가하면서 확인했기 때문에 중복으로 확인할 필요가 없기 때문입니다. 그 후 만약 이 사다리가 잘못된 경우 다음 위치에 사다리를 추가할 수 있도록 추가한 사다리를 없애줍니다.

 

말로 이해가 잘 안된다면 밑에 코드에 주석을 달아놨습니다.

천천히 보시면 이해가 될 것입니다.

 

전체코드

#include <iostream>
using namespace std;
int n, m, h;
bool ladder_pos[31][11];
int ladder_cnt; // 가로선을 추가할 개수
bool flag = false;
 
void dfs(int y, int cnt){
    if(ladder_cnt == cnt){
        bool possible = true; // 각각의 세로선이 잘 도착했는지 여부체크
        for (int i = 1; i <= n; i++){ // 세로선
            int verti = i;
            for (int j = 0; j < h; j++){ // 가로선
                int hight = j;
 
                if(ladder_pos[hight][verti]){ // 오른쪽으로 가는 경우
                    verti++;
                }else if(verti > 1 && ladder_pos[hight][verti - 1]){
                    //왼쪽으로 가는 경우
                    verti--;
                }
            }
            if(verti != i){ // 잘못된 세로선
                possible = false; 
                break;
            }
        }
        if(possible){
            flag = true; // 정답
        }
        return;
    }
 
    // 가로선 추가하는 코드
    for (int i = y; i < h;i++){
        for (int j = 1; j < n; j++){
            if(!ladder_pos[i][j-1] && !ladder_pos[i][j] && !ladder_pos[i][j+1]){
                //사다리가 추가 될 수 있는 위치인지 확인
                ladder_pos[i][j] = true; // 사다리 추가
                dfs(i, cnt + 1); // y좌표와 사다리 추가 개수 카운트
                ladder_pos[i][j] = false; // 추가한 사다리 삭제
            }
        }
    }
    return;
}
 
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m >> h;
 
    for (int i = 0; i < m; i++){   
        int a, b;
        cin >> a >> b;
        ladder_pos[a-1][b] = true; //문제에서 준 가로선 표시
    }
 
    for (int i = 0; i <= 3; i++){ // 가로선 추가 개수마다 확인
        ladder_cnt = i;
        dfs(0, 0);
        if(flag){ // 정답을 찾은 경우
            cout << ladder_cnt << endl;
            return 0;
        }
    }
 
    cout << -1 << endl; // 정답을 찾지 못한 경우
    return 0;
}

 

체감 난이도	걸린시간	후기	사용 알고리즘
중상	1.5h	처음에 문제를 어떻게 풀어야할 지 감을 못잡았음 어떤식으로 접근하는지 참고 후에 풀림	DFS 백트래킹