[백준 15684 사다리조작] -JAVA //le_effort

사다리 조작

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	29294	7732	3343	20.574%

문제

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

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

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

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

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

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을 출력한다.

예제 입력 1 복사

2 0 3

예제 출력 1 복사

xxxxxxxxxx
0

예제 입력 2 복사

xxxxxxxxxx
2 1 3
1 1

예제 출력 2 복사

xxxxxxxxxx
1

예제 입력 3 복사

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

예제 출력 3 복사

xxxxxxxxxx
3

예제 입력 4 복사

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

예제 출력 4 복사

xxxxxxxxxx
3

예제 입력 5 복사

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

예제 출력 5 복사

xxxxxxxxxx
-1

예제 입력 6 복사

xxxxxxxxxx
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

예제 출력 6 복사

xxxxxxxxxx
-1

예제 입력 7 복사

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

예제 출력 7 복사

xxxxxxxxxx
2

힌트

예제 3	예제 3 정답
예제 7	예제 7 정답

 

풀이

삼성 기출 골드 5 문제

근데 다른 골드 4 혹은 골드 3 문제보다 나는 더 어려웠다. 왜 이게 골드5지?

풀이는 dfs를 통해 하는건데

핵심은 시간초과 + 조합 개념을 이해 하는 것이다.

맨 처음은 시간초과를 못잡아서 시간초과가 엄청 나고

시간초과를 해결하니 조합 개념에 햇갈려서 엄청 틀렸다 ㅎ;;

 

일단 문제보자마자 ?_? 이였다

아니 사다리를 연결하는 건 어떻게 표현하며 어떻게 사다리를 탈 까?

 

우선 사다리가 연결 되는걸 표현 하는건

map[4] [1] map [4] [2] 이게 연결 돼 있다고 치면

map[4] [1] 이쪽에만 1로 표시했다

 

즉 map[x] [y]에 1 이라는 값이 들어있으면 map[x] [y+1] 과 연결 돼 있다는 식으로 표현을 했다.

그럼 map[x] [y]와 map[x] [y-1]이 연결 돼 있는건 어떻게 알 수 있을까?

map[x] [y]기준으로 map[x] [y-1]==1 이면 연결 돼 있다

즉 [x] [y] 기준으로 양옆의 연결 상태를 확인 할 수 있는 것이다.

 

그리고 일단 사다리는 최소 0개에서 최대 3개까지 놓을 수 있다

그래서 나는 dfs를 이런식으로 표현했다.

 

xxxxxxxxxx
    for(int i=0; i<=3; i++) {
            dfs(0,i,1);
        }
// public static void dfs(int level, int num, int col) 

dfs를 보면 인자로 level, num , col 이 있다

level은 지금 현재 사다리를 설치한 개수, num은 최대 사다리를 설치 할 수 있는 개수, col은 조합에 관련된건데 밑에서 다루도록 하겠다

 

즉 0개부터 3개까지 사다리를 각각 dfs 돌려주면서 확인해준다.

 

 

dfs함수

xxxxxxxxxx
public static void dfs(int level, int num, int col) {
        if(level>num || level >min) {
            return ;
        }
        if(isPossible()) {
            min = Math.min(min,level);
            System.out.println(min);
            System.exit(0);
            return ;
        }
        for(int i=col; i<=h; i++) {
            for(int j=1; j<=n; j++) {
                if(map[i][j]==0 && map[i][j-1]==0 && map[i][j+1]==0) {
                    map[i][j]=1;
                    dfs(level+1,num,i);
                    map[i][j]=0;
                }
            }
        }
    }

여기서 조합에 관련된게 나온다.

나는 맨처음에 dfs를 할때 (level+1,num,i+1) 이렇게 해야 된다고 생각했는데

그렇게 되면 반례가 생긴다.

 

 

i번째 선이 i번째로 아웃이 되는지 확인하는 메소드다.

    public static boolean isPossible() {
        for(int i=1; i<=n; i++) {
            int line = i;
            int col = 1;
            while(true) {
                if(col == h+1) {
                    break;
                }
                if(map[col][line]==1) { // 옆칸에 연결 돼 있는거
                    line+=1;
                }
                else if(map[col][line-1] ==1) {
                    line -=1;
                }
                col++;
            }
            
            if(line != i) {
                return false;
            }
        }
        return true;
    }

 

전체코드

import java.io.*;
import java.util.*;
public class Main {
    static int n,m,h;
    static int map[][];
    static int min = 4;
    static boolean end = false;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String [] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        m = Integer.parseInt(t[1]);
        h = Integer.parseInt(t[2]);
        
        map = new int[h+2][n+2];
        
        for(int i=0; i<m; i++) {
            String [] tt = br.readLine().split(" ");
            int a = Integer.parseInt(tt[0]);
            int b = Integer.parseInt(tt[1]);
            map[a][b]=1;
        }
​
        
        for(int i=0; i<=3; i++) {
            dfs(0,i,1);
        }
        System.out.println(-1);
    }
    public static void dfs(int level, int num, int col) {
        if(level>num || level >min) {
            return ;
        }
        if(isPossible()) {
            min = Math.min(min,level);
            System.out.println(min);
            System.exit(0);
            return ;
        }
        for(int i=col; i<=h; i++) {
            for(int j=1; j<=n; j++) {
                if(map[i][j]==0 && map[i][j-1]==0 && map[i][j+1]==0) {
                    map[i][j]=1;
                    dfs(level+1,num,i);
                    map[i][j]=0;
                }
            }
        }
    }
    public static boolean isPossible() {
        for(int i=1; i<=n; i++) {
            int line = i;
            int col = 1;
            while(true) {
                if(col == h+1) {
                    break;
                }
                if(map[col][line]==1) { // 옆칸에 연결 돼 있는거
                    line+=1;
                }
                else if(map[col][line-1] ==1) {
                    line -=1;
                }
                col++;
            }
            
            if(line != i) {
                return false;
            }
        }
        return true;
    }
}