[백준] 15684 사다리 조작 풀이 Python, Java

문제 페이지

---

---

접근방법

백트래킹

이미 문제에도 명시가 되어 있듯이 정답이 3보다 큰 값이거나 불가능한 경우에 -1을 출력합니다.

즉, 재귀함수의 depth에 제약을 걸어 가지치기를 할 수 있다는 말입니다.

저는 depth가 3에 도달하게 되면 더 이상 재귀 함수를 돌지 않게 설정했습니다.

로직

1. 2차원 Array 형태로 사다리 Map을 그려준다
2. 우측으로 이동하는 사다리는 1, 좌측으로 이동하는 사다리는 -1을 넣어준다. 내려가는 사다리는 0이다.
3. 모든 설치 가능한 구역에 사다리를 설치하는 브루트포스 문제이다. 그렇기 때문에 모든 구간을 순회하는 DFS를 사용한다.
   1. 각 사다리 별로 번호에 맞게 내려오는지 확인한다.
      1. 만약 맞다면, 정답을 갱신한다
      2. 만약 틀리다면, 가로 사다리를 계속해서 설치한다.

---

Python Code

N,M,H = map(int,input().split())
ladders = [[0]*N for _ in range(H)]
answer = -1
for i in range(M):
    a,b = map(int,input().split())
    ladders[a-1][b-1]=1
    ladders[a-1][b]=-1

def checkLadders():
    for ladder in range(N):
        x = ladder
        y = 0
        moved = False
        while y<H:
            if ladders[y][x]==0 or moved:
                y+=1
                moved = False
            elif ladders[y][x]==1 and not moved:
                x+=1
                moved = True
            elif ladders[y][x]==-1 and not moved:
                x-=1
                moved = True
        if x!=ladder:
            return False
    return True

def dfs(depth, number):
    global answer
    if checkLadders():
        if answer==-1:answer = depth
        else: answer = min(answer,depth)
        return
    if depth == 3:
        return    
    for next_number in range(number,N*H):
        x,y = next_number%N, next_number//N
        if ladders[y][x]==0:
            if x+1<N and ladders[y][x+1]==0:
                ladders[y][x]=1
                ladders[y][x+1]=-1
                dfs(depth+1,next_number+1)
                ladders[y][x]=0
                ladders[y][x+1]=0                

dfs(0,0)
print(answer)

Java Code

import java.util.*;
import java.io.*;

public class boj_15684_사다리조작 {
	static StringBuilder sb = new StringBuilder();
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N,M,H,answer=-1;
	static int[][] ladders;	
	
	static boolean checkLadders() {		
		for(int i =0;i<N;i++) {
			int nx,ny;
			nx = i;
			ny = 0;
			boolean moved = false;// 연속이동불가
			while(ny<H) {
				if(ladders[ny][nx]==0 || moved) {//하강
					ny++;
					moved = false;
				}
				else if(ladders[ny][nx]==1 && !moved) {//우측
					nx++;
					moved = true;
				}
				else if(ladders[ny][nx]==-1 && !moved) {//좌측
					nx--;
					moved = true;
				}
			}//끝에 도달
			if(nx!=i) {//결과 값이 다름
				return false;
			}
		}
		return true;
	}
	
	static void solution(int depth,int number) {
		if(checkLadders()) {
			if(answer==-1)answer=depth;
			else answer = Math.min(answer, depth);
			return;
		}
		if(depth == 3) {
			return;
		}
		for(int next_number = number;next_number<N*H;next_number++) {
			int x = next_number%N;
			int y = next_number/N;
			if(ladders[y][x]==0) {
				if(x+1<N&&ladders[y][x]==0&&ladders[y][x+1]==0) {//오른쪽 설치가능
					ladders[y][x]=1;
					ladders[y][x+1]=-1;
					solution(depth+1,next_number+1);
					ladders[y][x]=0;
					ladders[y][x+1]=0;		
				}
			}
		}
	}
	
	static void input() throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); //사다리 갯수
		M = Integer.parseInt(st.nextToken()); //가로선 갯수
		H = Integer.parseInt(st.nextToken()); //높이
		ladders = new int[H][N];
		//0 하강, 1 오른쪽, -1 왼쪽
		for(int i =0;i<M;i++) {
			int a,b;
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken())-1;
			b = Integer.parseInt(st.nextToken())-1;
			ladders[a][b] = 1;
			ladders[a][b+1] = -1;
		}
	}

	public static void main(String[] args) throws IOException {
		input();
		solution(0,0);			
		System.out.println(answer);
	}
}