BOJ 15684번: 사다리 조작

문제

문제 바로가기> BOJ 15684번: 사다리 조작

15684번: 사다리 조작

 

풀이

 

** 시간 초과 방지를 위한 Tip **

1. h번 가로선에서 사다리를 조작한 경우, 그 다음 조작할 사다리는 h번 가로선 부터 찾아가면 된다.

  → 이미 앞에서 계산했으므로 ! (이 부분이 중요 )

 

2. 가로선을 연속해서 나란히 놓을 필요가 없기 때문에,

`isLine[a][b] || isLine[a][b+1] || isLine[a][b-1]` 다음 중 하나라도 해당 된다면, 가로선을 놓을 필요가 없다.

 

3. maxcnt(최대 놓을 수 있는 사다리 개수)를 0에서 3까지 순차적으로 설정해주고 탐색을 진행한다.

  → 탐색을 진행하다 ans 값이 갱신된다면, 더 이상 탐색을 진행할 필요가 없다!

 

C++

#include<iostream>
#include<vector>
#define MAX_H 31
#define MAX_N 11
#define IMPOSSIBLE 4
using namespace std;

int N, M, H;
int ans = IMPOSSIBLE;
bool isLine[MAX_H][MAX_N];

void input() {
	cin >> N >> M >> H;

	int a, b;
	for (int i = 0; i < M; i++) {
		cin >> a >> b; // 1 ≤ a ≤ H , 1 ≤ b ≤ N-1
		isLine[a][b] = true; // 입력으로 주어지는 가로선이 서로 연속하는 경우는 없음
	}
}

bool ispossible() {
	for (int n = 1; n <= N; n++) { // 세로선
		int col = n;
		for (int h = 1; h <= H; h++) {
			if (isLine[h][col]) col++;
			else if (isLine[h][col - 1]) col--;
		}
		if (col != n) return false; // i번 세로선의 결과 != i번
	} return true;
}

void solution(int cnt, int row, int maxcnt) {
    if(cnt == maxcnt){
        if(ispossible()) ans = maxcnt; // i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려면, 추가해야 하는 가로선 개수의 최솟값
        return;
    }
    for (int a = row; a <= H; a++) {
		for (int b = 1; b < N; b++) {
			if (isLine[a][b] || isLine[a][b+1] || isLine[a][b-1]) continue; // 이미 가로선이 있는 경우, 서로 연속하는 경우
			isLine[a][b] = true;
			solution(cnt + 1, a, maxcnt);
			isLine[a][b] = false;
		}
	}
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    for(int maxcnt=0; maxcnt<4 && ans==IMPOSSIBLE; maxcnt++) solution(0, 1, maxcnt);
    ans == IMPOSSIBLE ? cout << -1 : cout << ans;
}

 

Java

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

public class Main {
	
	static final int IMPOSSIBLE = 4;
	static int ans = IMPOSSIBLE;
	
	static int N, M, H;
	static boolean[][] isLine;
	
	
	public static void main(String[] args) throws Exception {
		// System.setIn(new FileInputStream("res/input.txt"));
		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());
		isLine = new boolean[H+1][N+1];
		
		int a, b;
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			isLine[a][b] = true; // 입력으로 주어지는 가로선이 서로 연속하는 경우는 없음
		}
		
	    for(int maxcnt=0; maxcnt<4 && ans==IMPOSSIBLE; maxcnt++) solution(0, 1, maxcnt);
	    if(ans == IMPOSSIBLE) System.out.println(-1);
	    else System.out.println(ans);
		
	}
	
	static void solution(int cnt, int row, int maxcnt) {
	    if(cnt == maxcnt){
	        if(ispossible()) ans = maxcnt; // i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려면, 추가해야 하는 가로선 개수의 최솟값
	        return;
	    }
	    for (int a = row; a <= H; a++) {
			for (int b = 1; b < N; b++) {
				if (isLine[a][b] || isLine[a][b+1] || isLine[a][b-1]) continue; // 이미 가로선이 있는 경우, 서로 연속하는 경우
				isLine[a][b] = true;
				solution(cnt + 1, a, maxcnt);
				isLine[a][b] = false;
			}
		}
	}
	
	static boolean ispossible() {
		for (int n = 1; n <= N; n++) { // 세로선
			int col = n;
			for (int h = 1; h <= H; h++) {
				if (isLine[h][col]) col++;
				else if (isLine[h][col - 1]) col--;
			}
			if (col != n) return false; // i번 세로선의 결과 != i번
		} return true;
	}
}