글 읽기 - [15684] 사다리 조작 질문드립니다 (Java)

zpgy77 5년 전 0

시간 초과가 발생하는데 여기서 어떤 방식으로 개선을 해야 할지 모르겠습니다.

접근 방법이 잘못된 것은 아닌것 같은데 개선방법이 떠오르지 않습니다ㅠㅠ

읽어주셔서 감사합니다.

import java.util.*;

public class Main {
	
	static int[][] field;
	static boolean found = false;
	static int N,M,H;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		H = sc.nextInt();
		int res = -1;
		
		field = new int[H+1][N+1];
		
		for (int i = 0; i < M; i++) {
			int inputX = sc.nextInt();
			int inputY = sc.nextInt();
			field[inputX][inputY] = 1;
		}
		
		for (int latter = 0; latter <= 3; latter++) {
			generateLadders(latter,1);
			if (found) {
				res = latter;
				break;
			}
		}
		System.out.println(res);
	}

	private static void generateLadders(int count, int x) {
		if (!found) {
			if (count==0) {
				found = check();
			}
			
			if (found) return;
			
			for (int i = x; i <= H; i++) {
				for (int j = 1; j < N; j++) {
					if (field[i][j-1] == 1 || field[i][j] == 1 || field[i][j+1] == 1) {
						continue;
					}
					field[i][j] = 1;
					generateLadders(count-1, i);
					field[i][j] = 0;
				}
			}
		} 
	}
	

	private static boolean check() {
		for (int i = 1; i <= N; i++) {
			int y = i;
			for (int x = 1; x <= H; x++) {
				if (field[x][y] == 1) {
					y += 1;
				} else if (field[x][y-1] == 1) {
					y -= 1;
				}
			}
			if (i != y) {
				return false;
			}
		}
		return true;
	}
	
	private static void printField() {
		for (int i = 1; i <= H; i++) {
			for (int j = 1; j <= N; j++) {
				System.out.print(field[i][j] + " ");
			}
			System.out.print("\n");
		}
		System.out.print("\n");
		System.out.print("\n");
	}

}

zpgy77 5년 전 0

해결했습니다. check()하는 부분에 return을 빼먹었었네요....

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[15684] 사다리 조작 질문드립니다 (Java)

zpgy77 5년 전 0

zpgy77 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말