BOJ 15684 사다리조작 java 자바 + dfs 풀이 추가

BOJ 15684 사다리조작 java 자바

 

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

15684번: 사다리 조작

 

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

public class BOJ_15684_사다리조작 {
	static int N, M, H;
	static int[][] ori_ledder;
	
	static class Ledder implements Comparable<Ledder>{
		int cnt; // 사다리 추가로 놓은 개수
		int[][] ledder;	// 사다리 상태
		int[] last; // 마지막으로 사다리 놓은 위치
		public Ledder(int cnt, int[][] ledder, int[] last) {
			this.cnt = cnt;
			this.last = last;
			this.ledder = ledder;
		}
		@Override
		public int compareTo(Ledder o) {
			return this.cnt - o.cnt;
		}
	}
	
	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());
		
		ori_ledder = 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());
		
			ori_ledder[a][b] = 1;
		}
		
		if(check(ori_ledder)) {	// 자기 번호로 가는 사다리가 완성되면
			System.out.println(0);
		} else {
			if(N == 0) System.out.println(-1);
			else System.out.println(solve());
		}
		
	} // main
	
	private static int solve() {
		PriorityQueue<Ledder> pq = new PriorityQueue<>();
		pq.offer(new Ledder(0, ori_ledder, new int[] {0,1}));
		
		Ledder p;
		while(!pq.isEmpty()) {
			p = pq.poll();
			
			// 사다리 가능한 곳 하나에 놓는다.
			int[][] copy = new int[H+1][N+1];
			for (int i = 1; i <= H; i++) {
				for (int j = 1; j <= N; j++) {
					copy[i][j] = p.ledder[i][j];
				}
			}
			// 사다리 가능한 곳 찾기
			int i = p.last[0];
			int j = p.last[1];
			
			if(j == N-1 && i == H) {	// 사다리를 더 이상 놓을 수 없는 경우는 안 됨
				continue;
			}
			
			boolean canPutLedder = false;
			while(true) {
				i++;
				if(i == H+1) {
					i = 1;
					j++;
					if(j == N) {	// 사다리를 더 이상 놓을 수 없는 경우는 안 됨
						break;
					}
				}
				if(copy[i][j] == 0) {
					if(j == 1) {
						if(j < N-1) {
							if(copy[i][j+1] == 0) {
								canPutLedder = true;
								break;
							}
						} else {
							canPutLedder = true;
							break;
						}
					} else if(j > 1 && copy[i][j-1] == 0) {
						if(j < N-1) {
							if(copy[i][j+1] == 0) {
								canPutLedder = true;
								break;
							}
						} else {
							canPutLedder = true;
							break;
						}
							
					}
				}
			}
			if(!canPutLedder) continue;
			copy[i][j] = 1;
			
			if(check(copy)) {	// 자기 번호로 가는 사다리가 완성되면
				return p.cnt+1;
			}
			
			pq.offer(new Ledder(p.cnt, p.ledder, new int[] {i, j}));
			if(p.cnt+1 == 3) {	// 추가 사다리를 이미 2개 + 1 놓은 경우는 안 됨
				continue;
			}
			pq.offer(new Ledder(p.cnt+1, copy, new int[] {i, j}));
		}
		
		return -1;
	} // solve

	private static boolean check(int[][] arr) { // 자기 번호로 가는 지 체크하는 함수
		for (int num = 1; num <= N; num++) {
			
			int i = 1, j = num;
			while(true) {
				if(i == H+1) break;
				
				if(j > 1 && arr[i][j-1] == 1) { // 왼쪽에 있는 상황
					j--;
				} else if(arr[i][j] == 1){	// 오른쪽에 있는 상황
					j++;
				}
				i++;
			} // while
			
			if(j != num) return false;
		}
		
		return true;
	} // check
	
}

 

 

무려 1시간 34분 걸린 문제 ㅋㅋㅋㅋㅋㅋㅋㅋ

조건을 잘못 줘서 오류 찾느라 진땀뺌..

 

BFS 로 풀어서 엄청난 시간과 메모리.. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

풀고 나서 다른 사람 코드들을 보니 DFS로 빠르고 적은 메모리로 풀 수 있었다..

 

DFS 로 변형한 코드를 다시 추가해야겠다.

일단 BFS로는 사다리를 놓을 수 있는 칸을 찾아서 그 칸에 놓고(배열 복사) PriorityQueue 에 넣는다.

이 떄 사다리를 안 놓는 경우도 PriorityQueue에 넣는다.

pq.offer(new Ledder(p.cnt, p.ledder, new int[] {i, j}));
pq.offer(new Ledder(p.cnt+1, copy, new int[] {i, j}));

 

pq 로 하기 때문에 사다리가 적은 순서대로 나온다.

 

지금 생각해보니 DFS로 하면 배열 복사 필요없이 사다리를 놓는 경우 / 안 놓는 경우 

바로 해볼 수 있겠구나 싶다.

 

일단 기록용으로 BFS를 남겨두고..

코드가 너무 복잡하고 가독성이 안 좋아서 DFS 로 변형한 코드를 다시 추가해야겠다.

 

 

++ dfs 추가

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

public class BOJ_15684_사다리조작_dfs {
	static int N, M, H;
	static int[][] ori_ledder;
	
	static class Ledder implements Comparable<Ledder>{
		int cnt; // 사다리 추가로 놓은 개수
		int[][] ledder;	// 사다리 상태
		int[] last; // 마지막으로 사다리 놓은 위치
		public Ledder(int cnt, int[][] ledder, int[] last) {
			this.cnt = cnt;
			this.last = last;
			this.ledder = ledder;
		}
		@Override
		public int compareTo(Ledder o) {
			return this.cnt - o.cnt;
		}
	}
	
	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());
		
		ori_ledder = 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());
		
			ori_ledder[a][b] = 1;
		}
		
		if(check()) {	// 자기 번호로 가는 사다리가 완성되면
			System.out.println(0);
		} else {
			if(N == 0) System.out.println(-1);
			else {
				solve(1, 1, 0);
				System.out.println(MIN > 3? -1 : MIN);
			}
		}
		
	} // main
	
	static int MIN = 4;
	private static void solve(int r, int c, int cnt) {
		if(cnt >= MIN-1) return;
		if(r >= H+1) {
			return;
		}
		
		if(c == N-1) {
			solve(r+1, 0, cnt);
		} else solve(r, c+1, cnt);
		
		if(ori_ledder[r][c] == 0) {
			if(c > 1 && ori_ledder[r][c-1] == 1) return;
			if(c < N && ori_ledder[r][c+1] == 1) return;
			
			ori_ledder[r][c] = 1;
			if(check()) {
				if(MIN > cnt+1) MIN = cnt+1;
			}
			if(c == N-1) {
				solve(r+1, 0, cnt+1);
			} else solve(r, c+1, cnt+1);
			ori_ledder[r][c] = 0;
		}
	} // solve

	private static boolean check() { // 자기 번호로 가는 지 체크하는 함수
		for (int num = 1; num <= N; num++) {
			
			int i = 1, j = num;
			while(true) {
				if(i == H+1) break;
				
				if(j > 1 && ori_ledder[i][j-1] == 1) { // 왼쪽에 있는 상황
					j--;
				} else if(ori_ledder[i][j] == 1){	// 오른쪽에 있는 상황
					j++;
				}
				i++;
			} // while
			
			if(j != num) return false;
		}
		
		return true;
	} // check
	
}

 

bfs

dfs

 

 

시간과 메모리가 매우매우매우 많이 줄었다.

check() 함수는 bfs 와 같다.

solve() 함수 코드가 엄청 줄었다.

 

열을 +1씩 하면서 그 자리에 사다리를 놓을 수 있다면 놓기 + 놓지 않기 를 반복한다.

solve(r, c+1, cnt);
ori_ledder[r][c] = 1;
solve(r, c+1, cnt+1);
ori_ledder[r][c] = 0;

↑ 이렇게 !

 

사다리를 하나씩 놓을 때마다 check 함수를 호출하여 자기 번호로 가는 사다리가 되었는 지 확인하여 MIN 갱신한다.