백준 15684 - 사다리 조작 JAVA

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

15684번: 사다리 조작

 

 

문제 해결하는 데 거의 2~3시간 걸린 거 같다.

처음 접근을 정말 바보 같이했다.

이차원 배열의 빈 공간을 조합(Combination)을 통해 사다리의 개수를 추가하려고 했다.

그러니 말도 안 되는 오류를 계속 뱉어내었다.

결국 코드를 지우고 다시 접근하여 해결하였다.

 

이차원 배열을 만들어주고 사다리의 연결 부분을 1과 2로 나누었다.

1에서 시작될 때는 오른쪽으로 이동, 2일 때는 왼쪽으로 이동을 의미한다.

 

사다리 개수 추가는 이중 for문을 이용하여 이차원 배열의 빈 곳을 찾았고 그 값의 왼쪽 값도 비어있다면 연결시켰다.

추가로 연결시킨 개수가 answer값과 같다면 (1~3) 사다리를 위에서 아래로 내려가 같은 세로선의 값이 나오는지를 확인한다.

같다면 finish라는 boolean형을 true로 만들어 모든 루프를 탈출하고 output을 뱉어내면 종료한다.

 

 

문제를 읽고 무턱대고 바로 구현을 하였다.

나오는 에러나 추가사항이 있다면 다시 수정하고 반복을 하였더니 점점 나의 코드가 지저분해지고 제대로 동작하지 않았다. 

앞으로 코드를 작성하기 전에 먼저 어떤 식으로 로직을 구현할지 어느 정도 틀을 정하고 깔끔하게 코드를 짜야겠다는 생각이 들었다.

 

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

public class 백준_사다리조작_15684 {
	private static int n, m, h, answer;
	private static int[][] map;
	private static boolean finish = false;

	public static void main(String[] args) throws Exception {
		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());
		// 인덱스를 맞추기위해서 (값이 1부터 시작함으로) 이차원 배열 +1를 해줌
		map = new int[h + 1][n + 1];
		int x, y;
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			x = Integer.parseInt(st.nextToken());
			y = Integer.parseInt(st.nextToken());
			map[x][y] = 1;
			map[x][y + 1] = 2;
		}
//		print();
		// 추가 갯수
		for (int i = 0; i <= 3; i++) {
			// answer은 최종 깊이를 의미
			answer = i;
			// 탐색 시작
			dfs(1, 0);
			// 제일 작은 값 리턴이니까 바로 break;
			if (finish)
				break;
		}
		System.out.println((finish) ? answer : -1);
	}

//	static void print() {
//		for (int i = 0; i < h + 1; i++) {
//			for (int j = 0; j < n + 1; j++) {
//				System.out.print(map[i][j] + " ");
//			}
//			System.out.println();
//		}
//		System.out.println();
//	}

	private static void dfs(int x, int count) {
		// 만일 하나를 추가했을때 맞았다면 전부 종료
		if (finish)
			return;
		// 깊이까지 전부 탐색하였을 때
		if (answer == count) {
			// check 이게 원하는 값까지 들어갔는 지 확인
			if (check())
				// finish를 true로 바꿔 주며 dfs 종료
				finish = true;
			return;
		}

		// 전체 맵 탐색하는데 j는 n+1를 계산하기위해 범위는 -1 적은 n 까지의 범위로 이중for문
		for (int i = x; i < h + 1; i++) {
			for (int j = 1; j < n; j++) {
				// 양 옆이 0일때 선 긋기
				if (map[i][j] == 0 && map[i][j + 1] == 0) {
					map[i][j] = 1;
					map[i][j + 1] = 2;
					// 재귀
					dfs(i, count + 1);
					// 재귀후 다시 원래 값으로 초기화
					map[i][j] = map[i][j + 1] = 0;
				}
			}
		}
	}

	// 선 연결후 동일한 세로값인지 확인
	private static boolean check() {
		for (int i = 1; i <= n; i++) {
			int x = 1, y = i;
			for (int j = 0; j < h; j++) {
				// 1이면 오르쪽으로
				if (map[x][y] == 1)
					y++;
				// 2이면 왼쪽으로
				else if (map[x][y] == 2)
					y--;
				// 아래로
				x++;
			}
			// 같지 않다면 false 졸료
			if (y != i)
				return false;
		}
		return true;
	}

}