[백준] 15684번 : 사다리 조작 Gold3(골드3) - JAVA[자바]

[Gold III] 사다리 조작 - 15684

문제 링크

성능 요약

메모리: 14204 KB, 시간: 312 ms

분류

백트래킹, 브루트포스 알고리즘, 구현

제출 일자

2024년 1월 31일 15:41:53

문제 설명

사다리 게임은 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이라면 0을 바로 출력해주면 됨

3. 0개를 놓을 수 있는 상황과 1,2,3개를 놓을 수 있는 상황을 순차적으로 조합을 이뤄 확인한다.

4. 현재 놓여진 다리 상황이 유효한지 확인한다.

4. 만약 유효한 경우를 발견한 경우 출력 후 종료해준다.

 

세로선을 기준으로 가로선이 짝수개수인지 확인

// 가로선의 개수가 짝수여야 본인의 위치로 갈 수 있다.
	// -> 만약 가로선의 개수가 홀수인 것이 3개 이상이면 무조건 실패
	private static boolean isOddCount() {
		int count = 0;
		for (int i = 1; i <= N; i++) {
			int tmp = 0;
			// 현재 세로선에 연결된 가로선들의 개수를 구해줌
			for (int j = 1; j <= H; j++) {
				if (line[j][i] != 0) {
					tmp++;
				}
			}
			// 가로선의 개수가 홀수면 count 증가
			if (tmp % 2 != 0) {
				count++;
			}

			// 홀수인 것의 개수가 3개이상이면 false 리턴
			if (count > 3) {
				return false;
			}
		}

		return false;
	}

 

가로선이 0인 경우

// 가로선의 개수가 없다면 0을 출력함
		if (M == 0) {
			System.out.println(0);
			return;
		}

 

0~3까지 다리를 놓을 수 있는 조합 생성

// 현재 설치한 경로에서 각 줄로 갈 수 있는지 확인하는 메서드
	private static void lineInstall(int depth, int x, int limit) {
		// 현재 제한된 깊이만큼 다리를 설치하고 각 i번째 출발점이 i로 도착할 수 있다면 출력 후 종료
		if (depth == limit) {
			if (isPossible()) {
				System.out.println(limit);
				System.exit(0);
			}
			return;
		}

		for (int i = x; i <= H; i++) {
			for (int j = 2; j <= N; j++) {
				// 왼쪽을 바라보는 방향으로 설치가 가능한지만 확인하면 된다.(마지막은 오른쪽으로 설치 못하기에)
				int left = j - 1;
				// 왼쪽선이 연결되어있는 경우 넘어감
				if (line[i][left] != 0)
					continue;

				// 현재 위치가 연결된 상태고 오른쪽과 연결된 경우 다음다리까지 넘어가준다.
				if (line[i][j] != 0) {
					j++;
					continue;
				}

				// 왼쪽 세로선과 현재 위치 모두 비어있다면 연결하기
				line[i][j] = left;
				line[i][left] = j;
				lineInstall(depth + 1, i, limit);
				// 다시 줄을 초기화 시켜줌
				line[i][j] = line[i][left] = 0;
			}
		}
	}

 

현재 상태가 유효한지 확인

// 현재 상태로 i -> i로 내려갈 수 있는지 확인하는 메서드
	private static boolean isPossible() {
		for (int i = 1; i <= N; i++) {
			// 출발 지점 설정
			int x = 1, y = i;
			// 현재 x가 끝까지 내려간다면
			for (; x <= H; x++) {
				// 연결안된다면 쭉 내려간다.
				if (line[x][y] == 0)
					continue;
				// 연결된 곳을 찾았다면 y로 이동함
				y = line[x][y];
			}
			if (i != y) {
				return false;
			}
		}
		
		return true;
	}

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());

		line = new int[H + 1][N + 1];
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			// 두개를 서로 연결 시켜준다.
			line[a][b] = b + 1;
			line[a][b + 1] = b;
		}
		// 가로선의 개수가 없다면 0을 출력함
		if (M == 0) {
			System.out.println(0);
			return;
		}

		// 세로선이 자신의 선으로 가기 위해서는 가로선의 개수가 짝수여야 함.
		// 가로선은 최대 3개이기 때문에 가로선을 놓아야하는 수가 3개보다 크다면 -1 출력
		if (isOddCount()) {
			System.out.println(-1);
			return;
		}

		// 다리를 0개를 놓는 상황부터 3개를 놓는 상황까지 조합을 한다.
		for (int i = 0; i <= 3; i++) {
			lineInstall(0, 1, i);
		}

		System.out.println(-1);
	}

	// 현재 설치한 경로에서 각 줄로 갈 수 있는지 확인하는 메서드
	private static void lineInstall(int depth, int x, int limit) {
		// 현재 제한된 깊이만큼 다리를 설치하고 각 i번째 출발점이 i로 도착할 수 있다면 출력 후 종료
		if (depth == limit) {
			if (isPossible()) {
				System.out.println(limit);
				System.exit(0);
			}
			return;
		}

		for (int i = x; i <= H; i++) {
			for (int j = 2; j <= N; j++) {
				// 왼쪽을 바라보는 방향으로 설치가 가능한지만 확인하면 된다.(마지막은 오른쪽으로 설치 못하기에)
				int left = j - 1;
				// 왼쪽선이 연결되어있는 경우 넘어감
				if (line[i][left] != 0)
					continue;

				// 현재 위치가 연결된 상태고 오른쪽과 연결된 경우 다음다리까지 넘어가준다.
				if (line[i][j] != 0) {
					j++;
					continue;
				}

				// 왼쪽 세로선과 현재 위치 모두 비어있다면 연결하기
				line[i][j] = left;
				line[i][left] = j;
				lineInstall(depth + 1, i, limit);
				// 다시 줄을 초기화 시켜줌
				line[i][j] = line[i][left] = 0;
			}
		}
	}

	// 현재 상태로 i -> i로 내려갈 수 있는지 확인하는 메서드
	private static boolean isPossible() {
		for (int i = 1; i <= N; i++) {
			// 출발 지점 설정
			int x = 1, y = i;
			// 현재 x가 끝까지 내려간다면
			for (; x <= H; x++) {
				// 연결안된다면 쭉 내려간다.
				if (line[x][y] == 0)
					continue;
				// 연결된 곳을 찾았다면 y로 이동함
				y = line[x][y];
			}
			if (i != y) {
				return false;
			}
		}
		
		return true;
	}

	// 가로선의 개수가 짝수여야 본인의 위치로 갈 수 있다.
	// -> 만약 가로선의 개수가 홀수인 것이 3개 이상이면 무조건 실패
	private static boolean isOddCount() {
		int count = 0;
		for (int i = 1; i <= N; i++) {
			int tmp = 0;
			// 현재 세로선에 연결된 가로선들의 개수를 구해줌
			for (int j = 1; j <= H; j++) {
				if (line[j][i] != 0) {
					tmp++;
				}
			}
			// 가로선의 개수가 홀수면 count 증가
			if (tmp % 2 != 0) {
				count++;
			}

			// 홀수인 것의 개수가 3개이상이면 false 리턴
			if (count > 3) {
				return false;
			}
		}

		return false;
	}

}