[백준] 15684. 사다리 조작 (골드3) - DFS

Kiefer Sol·2024년 8월 8일

목록 보기

22/35

15684. 인구이동 (골드3)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	72966	19705	9624	22.072%

문제

사다리 게임은 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을 출력한다.

예제 입력 1
5 5 6
1 1
3 2
2 3
5 1
5 4

예제 출력 1
3

예제 입력 2
2 0 3

예제 출력 2
0

예제 입력 3
2 1 3
1 1

예제 출력 3
1

풀이

main
1.1 사다리타기가 진행중인지, 끝인지 파악하기 위해 finish 변수 선언
1.2. 입력받을 때, 받은 좌표의 오른쪽으로는 1, 왼쪽으로는 2표시 (왼쪽은 세로 좌표 -1)
1.3. 추가할 수 있는 사다리 3개 => 3번의 반복문
DFS 내려가서 finish가 true로 변하면 수를 출력한다.
3번을 초과하면 더 이상 사다리를 추가할 수 없다 => -1 출력
DFS 함수 (시작 가로 위치, 현재 사다리의 갯수, 최대 놓을 수 있는 사다리의 갯수)
2.1. finish 변수가 true이면 더 이상 진행 x, return
2.2. 현재 사다리의 개수가 max개 일 때, check 함수 호출해 확인하고, finish 변경
2.3. for(시작 가로위치 ~ H) / for (1 ~ L)
2.3.1 arr[r][c]와 왼쪽, 오른쪽이 0이 아니면 (사다리가 있으면) 설치 못하고 넘어가기
2.3.2 설치 가능하면, arr[r][c]=1, arr[r][c-1]=2 설치하기
2.3.3. DFS(시작 가로 위치+1, 현재 사다리의 갯수+1, 최대 놓을 수 있는 사다리의 갯수)
2.3.4. arr[r][c]=0, arr[r][c-1]=0로 사다리 설치 제거하기
체크함수
3.1. 세로 확인하기 (나간게 다시 들어오나), 가로 한칸씩 내려가기
3.2. 가로 내려가면서 배열값이 1이면 왼쪽으로 세로 이동, 2이면 오른쪽으로 세로이동
3.3. 만약 세로 나간게 다시 돌아오지 않았다면 return false

public class Search_15684 {
	public static int L,M,H;
	public static int[][] arr;
	public static boolean finish;
	public static void main(String[] args) throws IOException{

		 	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	        StringTokenizer st = new StringTokenizer(br.readLine());
	        L = Integer.parseInt(st.nextToken());
	        M = Integer.parseInt(st.nextToken());
	        H = Integer.parseInt(st.nextToken());

	        arr = new int[H+1][L+1]; 
            
	        finish = false; // 사다리타기가 진행중인지, 끝인지 파악하기 위해 변수 선언
	        
	        for (int i = 0; i < M; i++) {
	            st = new StringTokenizer(br.readLine());
	            int r = Integer.parseInt(st.nextToken());
	            int c = Integer.parseInt(st.nextToken());
	            arr[r][c] = 1; // 오른쪽 가로 표시
	            arr[r][c-1] = 2; // 왼쪽 가로 표시
	        }
	        
	        for (int i = 0; i <= 3; i++) { //추가할 수 있는 사다리 3개
	            DFS(1, 0, i);
	            if(finish) { // DFS 내려가서 finish가 true로 변하면 수를 출력한다. 
	            	System.out.println(i);
	            	System.exit(0);
	            }
	        }
            // 3번을 초과하면 더 이상 사다리를 추가할 수 없다
	        System.out.println(-1);

	    }
	
	//DFS(1, 0, i); => (시작 가로 위치, 현재 사다리의 갯수,최대 놓을 수 있는 사다리의 갯수)
	//nr이 없고 가로가 1부터 시작해도 된다. 하지만 시간이 늘어난다. => 높이가 내려가면서 사다리를 추가한다.
	public static void DFS(int nr, int cnt, int size) {
		if(finish) return;
	        if (cnt == size) {
	            if (check()) {
	            	finish = true;
	            }
	            return;
	        }

	        for (int r = nr; r <= H; r++) { //가로
	            for (int c = 1; c < L; c++) {//세로
	                if (arr[r][c] == 1) // 가로선은 서로 접하면 안 된다
	                    continue;
	                if (arr[r][c - 1] == 1) { //두 가로선이 연속하면 안된다, 왼쪽에 이미 있으면 놓을 수 없븜
	                    continue;
	                }
	                if (arr[r][c + 1] == 1) { //두 가로선이 연속하면 안된다, 오른쪽에 이미 있으면 놓을 수 없음
	                    continue;
	                }
	                arr[r][c] = 1; //오른쪽 
	                arr[r][c-1]=2; //왼쪽
	                DFS(r, cnt + 1, size);
	                arr[r][c] = 0;
	                arr[r][c-1]=0;
	            }
	        }
	    }

	public static boolean check() {
	        for (int i = 1; i <= L; i++) {
	            int now = i; //세로 사타리 타가면서 검사 나간게 다시 들어오나 검사
	            int start = 1; //가로 내려 가면서 검사
	            while (start <= H) {
	                if (arr[start][now] == 1) {
	                	now--;
	                } else if (arr[start][now] == 2) {
	                	now++; 
	                }
	                start++; //가로 칸 내려가기
	            }
	            if (i != now) //나간게 다시 들어오지 않으면 false
	                return false;
	        }
	        return true;
	    }
	    
	public static void print() {
			for(int i=0; i<=H; i++) {
				for(int j=0; j<=L; j++) {
					System.out.print(arr[i][j]+" ");
				}
				System.out.println();
			}
		}
}