[DFS] 15684번 사다리 조작

15684번 사다리 조작

 

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

 

문제

사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다.

초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안된다. 또, 가로선은 점선 위에 있어야 한다.

위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다.

사다리 게임은 각각의 세로선마다 게임을 진행하고, 세로선의 가장 위에서부터 아래 방향으로 내려가야 한다. 이때, 가로선을 만나면 가로선을 이용해 옆 세로선으로 이동한 다음, 이동한 세로선에서 아래 방향으로 이동해야 한다.

위의 그림에서 1번은 3번으로, 2번은 2번으로, 3번은 5번으로, 4번은 1번으로, 5번은 4번으로 도착하게 된다. 아래 두 그림은 1번과 2번이 어떻게 이동했는지 나타내는 그림이다.

사다리에 가로선을 추가해서, 사다리 게임의 결과를 조작하려고 한다. 이때, i번 세로선의 결과가 i번이 나와야 한다. 그렇게 하기 위해서 추가해야 하는 가로선 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 세로선의 개수 N, 가로선의 개수 M, 세로선마다 가로선을 놓을 수 있는 위치의 개수 H가 주어진다. (2 ≤ N ≤ 10, 1 ≤ H ≤ 30, 0 ≤ M ≤ (N-1)×H)

둘째 줄부터 M개의 줄에는 가로선의 정보가 한 줄에 하나씩 주어진다.

가로선의 정보는 두 정수 a과 b로 나타낸다. (1 ≤ a ≤ H, 1 ≤ b ≤ N-1) b번 세로선과 b+1번 세로선을 a번 점선 위치에서 연결했다는 의미이다.

가장 위에 있는 점선의 번호는 1번이고, 아래로 내려갈 때마다 1이 증가한다. 세로선은 가장 왼쪽에 있는 것의 번호가 1번이고, 오른쪽으로 갈 때마다 1이 증가한다.

입력으로 주어지는 가로선이 서로 연속하는 경우는 없다.

 

출력

i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려면, 추가해야 하는 가로선 개수의 최솟값을 출력한다. 만약, 정답이 3보다 큰 값이면 -1을 출력한다. 또, 불가능한 경우에도 -1을 출력한다.

 

예제 입력

2 0 3

2 1 3
1 1

5 5 6
1 1
3 2
2 3
5 1
5 4

6 5 6
1 1
3 2
1 3
2 5
5 5

5 8 6
1 1
2 2
3 3
4 4
3 1
4 2
5 3
6 4

5 12 6
1 1
1 3
2 2
2 4
3 1
3 3
4 2
4 4
5 1
5 3
6 2
6 4

5 6 6
1 1
3 1
5 2
4 3
2 3
1 4

 

예제 출력

0

1

3

3

-1

-1

2

 

해결방법

가능한 경우를 DFS+백트래킹을 통해 전부 해보는 완전탐색 문제이다

 

 

⭐️ 솔루션 ⭐️

문제의 조건으로 Depth 가 3 으로 주어졌다 → DFS + 백트래킹 !!!

사다리의 크기가 30x10 이고 depth 가 3 인 만큼 가지치기를 잘 활용하면 그렇게 많은 시간이 들지않았다

 

 

비트 마스킹

해당 노드의 다리 설치 정보를 저장하기 위해 비트마스킹을 사용했다

• map[i][j] == 0 (00) 양방향 모두 설치된 다리가 없음
• map[i][j] == 1 (01) 오른쪽 방향에 다리 설치
• map[i][j] == 2 (10) 왼쪽 방향에 다리 설치

 

또한 해당 노드의 왼쪽이든 오른쪽이든 다리가 존재한다면 이어진 다리는 만들 수 없기에 visited 배열을 통해 방문 처리를 해준다

 

 

 

소스코드

문제 해결 시간 : 1h 20m

메모리 : 1988 KB

시간 : 1384 ms

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 0
#define INF 987654321
using namespace std;

/*
 
 h : 주어진 가로선의 개수
 m : 세로선의 개수 (열)
 n : 가로선을 놓을 수 있는 실선의 개수 (행)
 
*/

int h,m,n,a,b,ans;
int map[31][11];
bool visited[31][11];

// 해당 노드와 오른쪽 노드 사이에 다리 설치
void installBridge(int r,int c){
    // 해당 노드
    // 비트마스킹으로 오른쪽 다리 정보 추가, 방문 처리
    map[r][c] |= (1 << 0);
    visited[r][c] = true;
    
    // 오른쪽 노드
    // 비트마스킹으로 왼쪽 다리 정보 추가, 방문 처리
    map[r][c+1] |= (1 << 1);
    visited[r][c+1] = true;
}

// 해당 노드와 오른쪽 노드 사이에 다리 삭제
void removeBridge(int r,int c){
    // 해당 노드
    // 비트마스킹으로 오른쪽 다리 정보 삭제, 방문 처리 취소
    map[r][c] &= ~(1 << 0);
    visited[r][c] = false;
    
    // 오른쪽 노드
    // 비트마스킹으로 왼쪽 다리 정보 삭제, 방문 처리 취소
    map[r][c+1] &= ~(1 << 1);
    visited[r][c+1] = false;
}

// 해당 위치에 다리를 설치할 수 있는지 확인
bool chkSide(int x,int y){
    if(visited[x][y+1]){
        return false;
    }else{
        return true;
    }
}

// 가로선의 개수만큼 사다리를 내려감
bool chkDown(int c){
    int x = 1;
    int y = c;
    
    for(int i=1; i<=n; i++){
        // 만약 오른쪽 방향에 다리가 존재한다면
        if(map[x][y] & (1 << 0))
            y++;
        // 만약 왼쪽 방향에 다리가 존재한다면
        else if(map[x][y] & (1<<1))
            y--;
        
        x++;
    }
    
    // 다 내려왔을 때 열의 번호가 일치한다면
    if(y == c) return true;
    else return false;
}

void dfs(int row,int cnt){
    // 불가능한 조건
    if(cnt > 3) return;
    if(cnt >= ans) return;
    
    // 정답을 찾은 경우
    if(cnt <= 3){
        bool flag = true;
        
        for(int i=1; i<=m; i++){
            if(!chkDown(i)){
                flag = false;
                break;
            }
        }
        // 모든 세로선의 결과가 자신으로 향한다면
        if(flag){
            ans = min(ans,cnt);
        }
    }
    
    // DFS 탐색 진행
    for(int i=row; i<=n; i++){
        for(int j=1; j<m; j++){
            // 사다리를 놓을 수 있다면?
            if(!visited[i][j] && chkSide(i,j)){
                installBridge(i,j);
                dfs(i,cnt+1);
                removeBridge(i,j);
            }
        }
    }
    
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> m >> h >> n;
    
    memset(visited, false, sizeof(visited));
    memset(map, 0, sizeof(map));
    
    for(int i=0; i<h; i++){
        cin >> a >> b;
        
        // 다리 설치
        installBridge(a,b);
    }
    
    ans = INF;
    dfs(1,0);
    
    if(ans == INF) cout << -1 << "\n";
    else cout << ans << "\n";
    
    return 0;
}