[백준 - Java] 15684번 : 사다리 타기

문제

www.acmicpc.net/problem/15684

15684번: 사다리 조작

설명

자잘한 실수도 많이 하고, 필요 없는 map을 만든다 거나, class로 좌표를 저장하고 ArrayList에 넣었다 뺐다, ArrayList를 복사하던가

삽질을 겁나 많이 했음.

막상 풀고나니 별거 없었고, 나는 4차원 배열까지 써서 해결했는데, 2차원 배열만 썼어도 됨...

삼성 SW역량테스트 기출문제인데, 나는 아마 주어진 3시간 동안 이 문제 계속 쩔쩔매다가 왔을 듯;;;;ㅜㅜ아웅ㅇ 열 받아!!!!!

 

 

가로선이 N열에서 시작한다면 N+1까지 이어짐.

그래서 boolean타입 4차원 배열을 사용해 가로선이 있는 경우 N열 -> N+1열 / N <- N+1 두 경우를 true로 저장

 

visited[a][b][a][b+1] = true;

visited[a][b+1][a][b] = true;

 

ex) (1, 1)에서 시작해 (1, 2)에서 끝나는 가로선은

1열 입장에서는 아래 코드와 같고, 

visited[1][1][1][2] = true;

 

2열 입장에서는 아래 코드와 같다.

visited[1][2][1][1] = true;

 

가로선을 놓는 것은 마치 조합을 구하는 알고리즘과 비슷하게 DFS를 사용해서 구현.

1, 2, 3 개수를 늘려가며 DFS로 모든 N * H의 좌표를 돌며 가로선을 놓아봄. (사다리 판을 2차원 배열처럼 생각하면 됨)

 

가로선을 놓았다면 check() 함수를 만들어 사다리를 타봄.

- i번 세로선이 i에 대응하면 성공, 그때의 가로선 개수를 출력하고 프로그램 종료.

- 대응할 수 없다면 계속해서 DFS 진행.

- 3까지 가로선을 놓아봤지만 성공할 수 없다면 -1을 출력하고 종료.

 

그리고 추가로 고려해야 할 점!

가로선이 하나도 없는 M = 0인 경우, -1을 출력하고 종료.

가로선을 추가 안 하고도 i번 세로선이 i에 대응한다면 성공, 0 출력하고 종료 

전체 코드

import java.util.Scanner;

public class Main {
	static int N, M, H;
	static boolean[][][][] visited;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		M = sc.nextInt();
		H = sc.nextInt();

		if(M == 0) { // 가로선 없는 경우 
			System.out.println("0");
			System.exit(0);
		}

		visited = new boolean[H+1][N+1][H+1][N+1];

		for(int i = 0; i < M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();

			visited[a][b][a][b+1] = true;
			visited[a][b+1][a][b] = true;
		}

		check(0); // 가로선을 추가 안해도 가능한 경우 

		for(int i = 1; i <= 3; i++) // 놓을 가로선 수 
			dfs(i, 0, i);

		System.out.println(-1); // 불가능 
	}


	// 조합을 구하는 알고리즘과 비슷하게 DFS로 추가할 가로선 개수 n만큼 가로선을 놓아봄 
	public static void dfs(int n, int depth, int cnt) {
		if(depth == n) { // n개의 가로선을 다 놓았을 때 		
			check(cnt); // i -> i 대응하는지 검사 

			return; // 재귀 종료 
		}
        
		// N-1에서 가로선 왼->오 (x, y) -> (x, y+1) / 오->왼 (x, y+1) -> (x, y) 다 설정하기 때문에 N까지만 
		for(int i = 1; i < H+1; i++) {
			for(int j = 1; j < N; j++) { 
				// 현재 좌표에 사다리가 있는 경우 
				if(j+1 < N+1 && visited[i][j][i][j+1]) { 
					j++; // 현재 열 + 2 부터 확인하면 됨 
					continue;
				} 
				// 현재 좌표 + 1(오른쪽)에 사다리가 있는 경우 
                else if(j+2 < N+1 && visited[i][j+1][i][j+2]) {
					j += 2; // 현재 열 + 3부터 확인하면 됨 
					continue;
				} 
				// 현재 좌표 - 1(왼쪽)에 사다리가 있는 경우 
                else if(j-1 > 0 && visited[i][j][i][j-1]) { 
					continue; 
				}

				// 조건 모두 통과 -> 가로선 놓아봄
				// 현재 좌표를 true로 만들어 가로선을 놓았다고 침 
				visited[i][j][i][j+1] = true; 
				visited[i][j+1][i][j] = true;

				// 가로선을 놓았으니 depth에 1을 추가하고 다시 DFS
				dfs(n, depth+1, cnt);

				// 다음 DFS를 위해 선택한 좌표를 false로 만들어 가로선 놓은걸 취소
				visited[i][j][i][j+1] = false; 
				visited[i][j+1][i][j] = false;
			}
		}
	}

	// i번 세로선이 i번에 대응하는지 검사 
	public static void check(int cnt) {
		for(int i = 1; i < N+1; i++) {
			int cx = 1; // 1행부터 시작해서 내려감 
			int cy = i;

			while(cx != H+1) { // H행을 넘을때까지 사다리 타기 
				// 현재 좌표 오른쪽에 가로선이 있는 경우 -> 오른쪽으로 이동 
				if(cy+1 < N+1 && visited[cx][cy][cx][cy+1]) cy = cy+1; 
				// 현재 좌표 왼쪽에 가로선이 있는 경우 -> 왼쪽으로 이동 
				else if(cy - 1 > 0 && visited[cx][cy][cx][cy-1]) cy = cy-1; 

				cx++; // 가로선이 있든 없든 아래로 내려감 
			}

			if(cy != i) return; // 실패 - i번 세로선의 결과가 i X
		}

		// 성공 - i번 세로선의 결과가 i번
		System.out.println(cnt);
		System.exit(0);
	}

}

 

* 비슷한데 다른 코드

DFS 수행 시, 현재 좌표, 현재 좌표 +1, 현재 좌표 -1 검사하는 것을 dy 배열과 for문으로 구현함.

 

import java.util.Scanner;

public class Main {
	static int N, M, H;
	static boolean[][][][] visited;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		M = sc.nextInt();
		H = sc.nextInt();

		if(M == 0) { // 가로선 없는 경우 
			System.out.println("0");
			System.exit(0);
		}

		visited = new boolean[H+1][N+1][H+1][N+1];

		for(int i = 0; i < M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();

			visited[a][b][a][b+1] = true;
			visited[a][b+1][a][b] = true;
		}

		check(0); // 가로선을 추가 안해도 가능한 경우 

		for(int i = 1; i <= 3; i++) { // 추가할 가로선 개수  
			dfs(i, 0, i);
		}

		System.out.println(-1); // 불가능 
	}

	// 조합을 구하는 알고리즘과 비슷하게 DFS로 추가할 가로선 개수 n만큼 가로선을 놓아봄 
	public static void dfs(int n, int depth, int cnt) {
		if(depth == n) { // n개의 가로선을 다 놓았을 때 		
			check(cnt); // i -> i 대응하는지 검사 

			return; // 재귀 종료 
		}
        
		// N-1에서 가로선 (x, y) -> (x, y+1) / (x, y+1) -> (x, y) 다 설정하기 때문에 N까지만 
		for(int i = 1; i < H+1; i++) {
			for(int j = 1; j < N; j++) { 
				// 현재 위치, 현재 -1 위치, 현재 +1 위치에 가로선을 놓을 수 있는지 검사 
				int[][] dy = {{0, 1}, {-1, 0}, {1, 2}}; 

				boolean flag = true;

				for(int k = 0; k < 3; k++) {
					int ny1 = j + dy[k][0];
					int ny2 = j + dy[k][1];
					
					// 범위 벗어나는 경우 pass 
					if(ny1 <= 0 || ny2 <= 0 || ny1 >= N+1 || ny2 >= N+1) 
						continue; 

					// 이미 다른 가로선이 있음 -> 놓을 수 X 
					if(visited[i][ny1][i][ny2]) {
						flag = false;
						break;
					}
				}

				if(flag) { // 조건 모두 통과 -> 가로선 놓아봄
					// 현재 좌표를 true로 만들어 가로선을 놓았다고 침 
					visited[i][j][i][j+1] = true; 
					visited[i][j+1][i][j] = true;

					// 가로선을 놓았으니 depth에 1을 추가하고 다시 DFS
					dfs(n, depth+1, cnt);

					// 다음 DFS를 위해 선택한 좌표를 false로 만들어 가로선 놓은걸 취소
					visited[i][j][i][j+1] = false; 
					visited[i][j+1][i][j] = false;
				}
			}
		}
	}

	// i번 세로선이 i번에 대응하는지 검사 
	public static void check(int cnt) {
		for(int i = 1; i < N+1; i++) {
			int cx = 1; // 1행부터 시작해서 내려감 
			int cy = i;

			while(cx != H+1) { // H행을 넘을때까지 사다리 타기 
				if(cy+1 < N+1 && visited[cx][cy][cx][cy+1]) { // 오른쪽에 가로선
					cy = cy+1; // 오른쪽 가로선으로 이동 
					cx++; // 아래로 내려감 
				} else if(cy - 1 > 0 && visited[cx][cy][cx][cy-1]) { // 왼쪽
					cy = cy-1; // 왼쪽 가로선으로 이동 
					cx++; // 아래로 내려감 
				} else { // 왼쪽, 오른쪽에 가로선이 둘 다 없음
					cx++; // 아래로 내려감 
				}
			}

			if(cy != i) return; // 실패 - i번 세로선의 결과가 i X
		}

		// 성공 - i번 세로선의 결과가 i번
		System.out.println(cnt);
		System.exit(0);
	}

}

GITHUB

github.com/KwonMinha/BOJ/blob/master/BOJ%2315684/src/Main.java

KwonMinha/BOJ