[백준온라인] 15684번 사다리 조작

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

15684번: 사다리 조작

 

문제 요약 : i번째로 출발해 i가 나오도록 선을 긋는 최소 횟수

입력	출력
2 ≤ N(열) ≤ 10 1 ≤ H(행) ≤ 30 0 ≤ M(사다리) ≤ (N-1)*H M개의 사다리값	i번째로 출발해 i가 나오게 만드는 최소 조작 횟수

 

JAVA - 수정 후

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
16394816	cbkpar	15684	맞았습니다!!	15592KB	1796ms	Java	1628B

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

public class Main {

	static int n,m,h;
	static int[][] ladder;
	static int ans = 4;
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int i;
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		h = Integer.parseInt(st.nextToken());

		ladder = new int[h][n];
		
		for(i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			ladder[Integer.parseInt(st.nextToken())-1][Integer.parseInt(st.nextToken())-1]=1;
		}
		if(m==0) {
			ans=0;
		}else {
		dfs(0,0);
		}
		ans=ans==4?-1:ans;
		bw.write(ans+"\n");
		br.close();
		bw.close();
	}
	static void dfs(int w, int k) {
		if(k>=ans) return; // 현재까지 구한 최솟값보다 같거나 크면 리턴
		int i;
		for(i=0;i<n-1;i++) { //n-1개가 똑같다면 나머지 하나는 당연히 같으므로 n까지 조사하지 않음
			int tmp = i;
			for(int j=0;j<h;j++) {
				if(ladder[j][tmp]==1) {//현재위치에 사다리가 있다면 오른쪽으로 한칸
					tmp++;
					continue;
				}
				if(tmp==0) continue;
				if(ladder[j][tmp-1]==1) {//현재위치-1에 사다리가 있으면 왼쪽으로 한칸
					tmp--;
					continue;
				}
			}
			if(tmp!=i) break;//시작한 사다리가 끝난 사다리와 다르면 종료
		}
		if(i==n-1&&k<ans) {//맞은 개수가 n-1개라면
			ans = k;
			return;
		}
		for(i=w;i<n*h;i++) {
			int dy = i/n;//초기값을 행렬안에 적지 않고 밖에 공통으로 적어줌
			int dx = i%n;
			if(i%n>0) {
				if(ladder[dy][dx-1]==1) continue; //왼쪽에 사다리가 있을경우 다음으로
			}
			if(i%n>=n-1) continue; //마지막에는 더이상 마지막으로 갈 수 없으므로 다음으로
			if(ladder[dy][dx+1]==1) continue; //오른쪽에 사다리가 있을 경우 다음으로
			if(ladder[dy][dx]==0) {
				ladder[dy][dx]=1;
				dfs(i+2,k+1);
                //사다리를 추가했을경우 연속할 수 없으므로 i+1이아닌 i+2로 한다.
				ladder[dy][dx]=0;
			}
		}
	}
}

느낀점 1: dy dx의 경우 i/n, i%n으로 행렬식 안에 넣었지만 이렇게 할경우 연산이 많아진다는 점 확인

 

느낀점 2: 연속할 경우에는 i+1번째가 아닌 그다음을 검사해도 된다.

 

느낀점 3: 1개만 틀릴 수 있는 경우는 존재 하지 않으므로 1번부터 n번까지 조사하지 않아도 된다.

 

느낀점 4:세로로 푸는것이아닌 가로로도 푸는 방법이 존재한다 행마다 열이 있는경우 결과를 바꿔주면된다.

//하지만 중간에 결과를 알 수 없고 끝까지 검사를 해야 한다는 단점이 있음

 

느낀점 5: 리스트로 미리 빈칸을 받거나 조건문을 개선하면 시간을 많이 단축 할 수 있을 것 같다.

 

 

 

 

 

JAVA

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
16385137	cbkpar	15684	맞았습니다!!	15812KB	2036ms	Java	1549B

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

public class Main {

	static int n,m,h;
	static int[][] ladder;
	static int ans = 4;
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int i;
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		h = Integer.parseInt(st.nextToken());

		ladder = new int[h][n];
		
		for(i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			ladder[Integer.parseInt(st.nextToken())-1][Integer.parseInt(st.nextToken())-1]=1;
		}
		dfs(0,0);
		ans=ans==4?-1:ans;
		bw.write(ans+"\n");
		br.close();
		bw.close();
	}
	static void dfs(int w, int k) {
		if(k>=ans) return;
		int i;
		for(i=0;i<n;i++) {
			int tmp = i;
			for(int j=0;j<h;j++) {
				if(ladder[j][tmp]==1) {
					tmp++;
					continue;
				}
				if(tmp==0) continue;
				if(ladder[j][tmp-1]==1) {
					tmp--;
					continue;
				}
			}
			if(tmp!=i) break;
		}
		if(i==n) ans=Math.min(ans, k);
		for(i=w;i<n*h;i++) {
			if(i%n>0) {
				if(ladder[i/n][i%n-1]==1) continue;
			}
			if(i%n>=n-1) continue;
			if(ladder[i/n][i%n+1]==1) continue;
			if(ladder[i/n][i%n]==0) {
				ladder[i/n][i%n]=1;
				dfs(i+1,k+1);
				ladder[i/n][i%n]=0;
			}
		}
	}
}