글 읽기 - Java - 시간 초과입니다.

taxol1203 2년 전 0

DFS 조합을 통하여 치킨집 2개를 뽑았으며,

2개의 치킨 집을 뽑을 때 마다, 모든 집에서 그 2개의 치킨 집 중에서의 최단거리(BFS)를 구했습니다.

10%에서 시간초과가 유발되는데, 제가 생각한 접근 방법이 틀렸는지 여쭤봅니다.

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

public class Main {
	static int n, m, result = Integer.MAX_VALUE;
	static boolean[][] graph;
	static int[] sel;	// 선택 된 치킨집
	static boolean[] vis;	// 방문 여부
	static int r1, r2;	// 결과를 담는 값
	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("res/mainInput.txt"));	//제출 할 때 주석해야함
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());
    	
    	graph = new boolean[n + 1][n + 1];
    	sel = new int[2];
    	
    	int a,b;
    	for(int i = 0; i < m; i++) {
    		stk = new StringTokenizer(br.readLine());
    		a = stoi(stk.nextToken());
    		b = stoi(stk.nextToken());
    		graph[a][b] = true;
    		graph[b][a] = true;
    	}
    	
    	DFS(0,1);
    	
    	System.out.println(r1 + " " + r2 + " " + result * 2);
    	br.close();
	}
	
	// 치킨 집 2개를 뽑는다.
	private static void DFS(int lv, int st) {
		if(lv == 2) {			
			int sum = 0;
			// 각 집에서 가장 짧은 치킨집을 고른다. 
			for(int i = 1; i <= n; i++) {
				if(sel[0] != i && sel[1] != i) {
					vis = new boolean[n + 1];
					vis[i] = true;
					sum += BFS(i);
				}
			}
			if(result > sum) {
				result = sum;
				r1 = sel[0];
				r2 = sel[1];
			}
			return;
		}
		for(int i = st; i <= n; i++) {
			sel[lv] = i;
			DFS(lv + 1, i + 1);
		}
	}
	
	// 하나의 집에서 2개의 치킨 집 중에서 최단 거리를 구한다.
	private static int BFS(int curN) {
		
		Queue<int[]> queue = new LinkedList<int[]>();
		queue.add(new int[] {curN, 0});
		int[] q;
		int cnt;
		while(!queue.isEmpty()) {
			q = queue.poll();
			curN = q[0];
			cnt = q[1];
			
			if(curN == sel[0] || curN == sel[1])
				return cnt;
			
			for(int i = 1; i <= n; i++) {
				if(!vis[i] && graph[curN][i]) {
					queue.add(new int[] {i, cnt + 1});
					vis[i] = true;
				}
			}
		}
		return -100000;
	}
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

kimensoo 1년 전 1

최단거리를 구하는 시점이 치킨집을 지정했을 때가 아니라 애초에 모든 빌딩 간의 거리를 구해놓고 치킨집을 지정하는 것이 효율적입니다.

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

문제

문제

출처

ICPC

Java - 시간 초과입니다.

taxol1203 2년 전 0

kimensoo 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말