글 읽기 - 사다리조작 9% 시간초과 (DFS - 백트랙) 제발 도와주세요...

cjsong 4년 전 0

DFS-백트랙 썻는데 시간을 더 줄일 방법이 있을가요 ??

1 . 맵에서 사다리를 설치가능한 곳 list에 담음

2. list크기만큼 조합을 통해 설치할 수 있는지 확인 후 설치

3. 설치 후 checkLadder() 함수를 통해 성공 여부 판별합니다.

제발 도와주세요...

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

public class Main15684_사다리조작2 {
	private static int N;
	private static int M;
	private static int H;
	private static int[][] map;
	private static ArrayList<Ladder> list;
	private static int result;
	private static boolean flag;

	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());
		map = new int[H + 1][N + 1];
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			map[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = 1;
		}

		list = new ArrayList<Ladder>();
		// 사다리를 놓을 수 있는 위치 계산
		for (int i = 1; i < map.length; i++) {
			for (int j = 1; j <= N - 1; j++) {
				if (j == 1) {
					if (map[i][j] == 0 && map[i][j + 1] == 0)
						list.add(new Ladder(i, j));

				} else if (j != 1 && j != N - 1) {
					if (map[i][j] == 0 && map[i][j - 1] == 0 && map[i][j + 1] == 0)
						list.add(new Ladder(i, j));
				} else if (j == N - 1) {
					if (map[i][j - 1] == 0 && map[i][j] == 0)
						list.add(new Ladder(i, j));
				}
			}
		}
//		print();
		flag = false;
		result = Integer.MAX_VALUE; // 사다리 최종 갯수
		backTracking(0, 0); // idx, 사다리 갯수
		result = result == Integer.MAX_VALUE ? -1 : result;
		System.out.println(result);
	}

	public static void backTracking(int idx, int ladderNum) {
		if(flag) return;
		if (ladderNum == 4 || idx == list.size())		return;
		
		flag = checkLadder(ladderNum);

		for (int i = idx; i < list.size(); i++) {
			Ladder ladder = list.get(i);
			if(map[ladder.r][ladder.c] == 0) {
				
				boolean check = checkInstall(ladder);	
				if(check ) {
					map[ladder.r][ladder.c]= 1;
//				print();
					backTracking(idx +1, ladderNum+1);
					map[ladder.r][ladder.c] = 0;
//				print();
				}
			}
		}
	}
	public static void print() {
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
		System.out.println("==============================");
	}

	private static boolean checkInstall(Ladder ladder) {
		if(ladder.c-1 >= 0 && map[ladder.r][ladder.c-1] == 1) return false;
		if(ladder.c+1 <= N  && map[ladder.r][ladder.c+1] == 1) return false;
		if(ladder.c-1 >= 0 && ladder.c+1 <= N && (map[ladder.r][ladder.c-1] == 1 || map[ladder.r][ladder.c+1] == 1)) return false;
		return true;
	}
	
	public static boolean checkLadder(int ladderNum) {
		for (int i = 1; i <= N; i++) {
			int startColumIdx = i;
			int startNum = 1;
			while (startNum <= H) {
				if (map[startNum][startColumIdx] == 1) {
					startColumIdx++;
					startNum++;
				} else if (startColumIdx-1 >= 1 && map[startNum][startColumIdx - 1] == 1) {
					startColumIdx--;
					startNum++;
				} else
					startNum++;
			}
			if (i == startColumIdx)
				continue;
			else
				return false;
		}
		result = result > ladderNum ? ladderNum : result;
		return true;
	}


public static class Ladder {
	int r;
	int c;

	public Ladder(int r, int c) {
		super();
		this.r = r;
		this.c = c;
	}

	@Override
	public String toString() {
		return "Ladder [r=" + r + ", c=" + c + "]";
	}

}}// end of class

ads1115 4년 전 0

저도 거기서 틀렸었는데 9%에서 멈추는 채점케이스가 답이 0이고 이때 종료하지 않으면 시간초과가 걸리는 케이스 인것 같더라구요. 한번 확인해보면 좋을 것 같아요.

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

문제

문제

출처

ICPC

사다리조작 9% 시간초과 (DFS - 백트랙) 제발 도와주세요...

cjsong 4년 전 0

ads1115 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말