글 읽기 - 6시간 동안 고통받고 있습니다.. 시간초과, 삼성기출

zaza1994 4년 전 0

질문게시판보니 옛날에는 테스트케이스가 있었던 것 같습니다. 지금은 없어서 어떤 부분에서 문제가 생기는지 모르겠습니다.

dfs로 풀었습니다.

다음 사다리를 만들 수 있는 위치를 찾고,

사다리 안만들고 dfs

사다리 만들고 dfs

그리고 중간중간 가장 작은 값보다 크면 리턴하게 만들었습니다.

어디서 시간초과가 나는거죠? 도와주세요

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

public class Main {
	static int N, M, H;
	static int[][] map;
	static int MINCOST;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		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());
		MINCOST = 4;
		
		map = new int[H+1][N];
		for(int m = 0; m < M; m++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			map[r][c] = 1;
		}
		
		dfs();
		if(MINCOST == 4) MINCOST = -1;
		System.out.println(MINCOST);
	}
	static void dfs() {
		dfs(0,1,1,false);
	}
	
	static void dfs(int count, int r, int c, boolean isCheck) {
		if(count >= MINCOST) return;
		
		if(!isCheck) {
			if(sol()) {
				if(MINCOST > count) MINCOST = count;
				return;
			}
		}
		
		int nr = r;
		int nc = c;
		
		
		// 다음 사다리를 만들 수 있는 곳 찾
		while(true) {
			
			if(map[nr][nc] == 0) {
				if(nc == 1 && N > 2) {
					if(map[nr][nc+1] != 1) break;
				} else if(nc == N-1) {
					if(map[nr][nc-1] != 1) break;
				} else {
					if(map[nr][nc+1] != 1 && map[nr][nc-1] != 1) break;
				}
			}
			
			nr++;
			if(nr == H+1) {nr = 1; nc++;}
			if(nc == N) break;
			
		}
		
		if(nc == N) return; 
	
		int[][] bu =  makeCp(map);
	
		// 사다리 안만들고 넘어가
		map[nr][nc] = -1;
		if(count >= MINCOST) return;
		dfs(count,nr,nc,true);
		
		// 사다리 만들고 넘어가
		map = makeCp(bu);
		map[nr][nc] = 1;
		if(count+1 >= MINCOST) return;
		dfs(count+1,nr,nc,false);		
		
	}
	
	static int[][] makeCp(int[][] ori){
		// map 백업 만드는 함
		int[][] ans = new int[H+1][N];
		for(int i = 0; i < H+1; i++) ans[i] = ori[i].clone();
		return ans;
	}
	
	static boolean sol() {
		
		int now = 0;
		
		for(int i = 1; i < N+1; i++) {
			now = i;
			for(int r = 1; r < H+1; r++) {
				if(now != N && map[r][now] == 1) now++;
				else if(map[r][now-1] == 1) now--;
			}
		
			if(now != i) return false;
		}
		
		return true;
	}
}

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

문제

문제

출처

ICPC

6시간 동안 고통받고 있습니다.. 시간초과, 삼성기출

zaza1994 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말