글 읽기 - [문명] 시간 초과 질문합니다.

sunminjeon 3년 전 0

BFS + 유니온파인드로 문제 풀었습니다.

다른 문제 풀이법을 보니 풀이법은 맞는 듯 한데, 계속 시간초과가 나옵니다.

어디서 가지치기를 할 수 있을까요 ?

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

public class Main {

	static int[] G = new int[100001];
	
	static List<Node> nodes;
	
	static int[][] list = new int[2001][2001];
	
	static Queue<Node> q = new LinkedList<Node>();
	static Queue<Node> q2 = new LinkedList<Node>();
	
	static int count;
	
    static int N,K;
    
    static int result;
    
    static final int[][] offset = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    
    static class Node{
    	int x;
    	int y;
    	
    	public Node() {}
    	public Node(int x, int y) {
    		this.x = x;
    		this.y = y;
    	}
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        int x,y,i,j = 0;
        
        result = 0;
        count = K;
        nodes = new ArrayList<Node>();
        q.clear();
        q2.clear();
        for(x = 1; x <= N; x++) {
        	for(y = 1; y <= N; y++) {
        		list[x][y] = 0;
        	}
        }
        for(x = 1; x <= K; x++) {
        	G[x] = x;
        }
        
        for(x = 1; x <= K; x++) {
        	st = new StringTokenizer(br.readLine());
        	int a = Integer.parseInt(st.nextToken());
        	int b = Integer.parseInt(st.nextToken());
        	nodes.add(new Node(a, b));
        	
        	list[a][b] = x;
        	G[x] = x;
        	
        	q.add(new Node(a,b));
        }
        
        while(count > 1) {
        	bfs_join();
        	if(count == 1) break;
        	
        	bfs();
        	result ++;
        }
        bw.append(result + "\n");
        
        bw.flush();
        bw.close();
        br.close();
    }
    
    static void bfs_join() {
    	while(!q.isEmpty()) {
    		Node startNode = q.poll();
    		int xx = startNode.x;
    		int yy = startNode.y;
    		int index = list[xx][yy];
    		
    		q2.add(new Node(xx,yy));
    		
    		for(int i=0; i < offset.length; i++) {
    			int x = startNode.x + offset[i][0];
    			int y = startNode.y + offset[i][1];
    			
    			// 범위 밖
    			if(x > N || y > N || x < 1 || y < 1) continue;
    			
    			int idx = list[x][y];
    			if(idx != 0 && find(index) != find(idx)) {
    				join(index, idx);
    				count --;
    			}
    		}
    	}
    }
    
    // 근처의 문명이 없는 곳을 확장
    static void bfs() {
    	while(!q2.isEmpty()) {
    		Node startNode = q2.poll();
    		int xx = startNode.x;
    		int yy = startNode.y;
    		int idx = list[xx][yy];
    		
    		for(int i=0; i < offset.length; i++) {
    			int x = startNode.x + offset[i][0];
    			int y = startNode.y + offset[i][1];
    			
    			// 범위 밖
    			if(x > N || y > N || x < 1 || y < 1) continue;
    			
    			if(list[x][y] != 0) continue;
    			
    			list[x][y] = idx;
    			q.add(new Node(x,y));
    		}
    	}
    }
    
    static int find(int a) {
    	// 문명이 없는 칸은 0, 문명이 있는 칸은 본인 
    	if(G[a] == a) return a;
    	return find(G[a]);
    }
    
    static void join(int a, int b) {
    	int A = find(a);
    	int B = find(b);
    	
    	G[A] = B;
    }
}

slah007 3년 전 0

union-find를 이렇게 작성하면 최악의 경우 find가 O(N)입니다. 시간복잡도 줄이는 법을 검색해보세요

sunminjeon 3년 전 0

헉 감사합니다.

유니온파인드의 find 함수를 return find(G[a]); 로 변경하니까 pass 하네요 !

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

문제

문제

출처

ICPC

[문명] 시간 초과 질문합니다.

sunminjeon 3년 전 0

slah007 3년 전 0

sunminjeon 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말