15684 사다리조작 - 삼성 sw 역량 기출

사다리조작

사다리 게임에서 i번에서 출발하면 i번에 도착하도록 사다리를 조작한다.

추가해야 하는 가로선의 최소값은? 만약 3보다 큰 값이면 -1을 출력한다.

---

###입력

boolean 이차원 배열을 통해 연결이 되어 있으면 true를 입력해줌

나중에 가장 마지막 세로선 오른쪽의 검사를 편하게 하기 위해 배열의 크기를 +2해줌

​

###구현

1. 모든 출발 점과 도착 점이 같은 x좌표를 가지는지 확인하는 chk메소드 구현

   오른쪽으로 가는 가로선만 true로 체크가 되어있기 때문에 현재 위치가 true가 아닐때 왼쪽의 상태도 체크해 주어야함

​

1. dfs 구현

   한칸씩 x좌표로 이동하면서 N보다 커지면 다음열의 첫번째로 갈 수 있도록 함

   종료조건 : 만든 가로선의 개수가 3개이거나 사다리의 마지막 (H, N) 에 도착했을 때 ( 배열을 크게 구현했으므로 배열의 마지막은 아님 )

   설치를 하지 않는 dfs 호출

   설치를 하는 dfs를 호출 하기 전에 가로선이 설치 되어 있는지 확인 ( 인접한 가로선이 있을 때에도 설치 할 수 없음 )

   설치를 하는 dfs 호출

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

public class Main사다리조작 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");

		N = Integer.parseInt(st1.nextToken());
		M = Integer.parseInt(st1.nextToken());
		H = Integer.parseInt(st1.nextToken());

		boolean[][] map = new boolean[H + 2][N + 2];
		for (int i = 0; i < M; i++) {
			StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
			int y = Integer.parseInt(st2.nextToken());
			int x = Integer.parseInt(st2.nextToken());
			map[y][x] = true;
		}

		ans = 4;

		dfs(1, 1, 0, map);

		if (ans > 3) {
			ans = -1;
		}
		System.out.println(ans);

	}

	static int ans;
	static int N;
	static int M;
	static int H;

	static void dfs(int y, int x, int cnt, boolean[][] map) {
		if(x == N+1) {
			y++;
			x=1;
		}

		// 종료조건 cnt가 3이거나 이미 마지막에 도착했을 때
		if(cnt == 3 || (x==N && y==H)) {
			if(chk(map)) {
				ans = Math.min(ans, cnt);
			}
			return;
		}

		dfs(y, x+1, cnt, map);

		// 가로선이 이미 존재할 때
		if(x == N ||  map[y][x] || (x!=1 && map[y][x-1]) || map[y][x+1]) return;

		map[y][x] = true;
		dfs(y, x+1, cnt+1, map);
		map[y][x] = false;
	}

	static boolean chk(boolean[][] map) {
		for(int i = 1; i <= N; i++) {
			int start = i;
			int end = i;
			for(int j = 1; j <= H; j++) {
				if(map[j][end]) {
					end++;
					continue;
				}
				if(end == 1) continue;
				if(!map[j][end]) {
					if(map[j][end-1]) {
						end--;
						continue;
					}
				}
			}
			if(start != end)return false;
		}
		return true;
	}
}
 ​