글 읽기 - 어느 부분에서 틀리는 지 모르겠습니다..

hswsua 6년 전 0

DFS로 카테고리를 나누고 BFS로 각 사람 마다 최대 값을 구한 다음 카테고리 별로 최소가 되는 값을 찾아 출력했습니다.

그런데 자꾸 틀리다고 나오네요... 반례나 코드 상 틀린 부분이 있다면 지적 부탁드립니다.

import java.util.*;

public class Main {
	
	static int N = 0;
	static int M = 0;
	static int[][] map = new int[10000][10000];
	static int[] v = new int[10000];
	static int[] bmax = new int[10000];
	static int[] max = new int[10000];
	
	
	void DFS(int start, int end){
		
		v[start] = end;
		
		for(int i=1; i<=N; i++){
			if(map[start][i] == 1 && v[i] == 0){
				DFS(i, end);
			}
		}
	}
	
	int BFS(int start){
		
		Queue<Integer> q = new LinkedList<Integer>();
		int[] v3 = new int[10000];
		int[] v2 = new int[10000];
		int vmax = 0;
		
		q.offer(start);
		v2[start] = 0;
		v3[start] = 1;
		
		while(!q.isEmpty()){
			int temp = q.poll();

			for(int i=1; i<=N; i++){
				if(map[temp][i] != 0 && v3[i] == 0){

					q.offer(i);
					v2[i] = v2[temp] + 1;
					v3[i] = 1;
										
				}
			}
		}
		
		for(int i=1; i<=N; i++){
			if(v2[i] > vmax){
				vmax = v2[i];
			}	
		}
		
		return vmax;
		
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
	
	Scanner sc = new Scanner(System.in);
	Main m = new Main();
	
	N = sc.nextInt();
	M = sc.nextInt();
	
	for(int i=0; i<M; i++){
		int a = sc.nextInt();
		int b = sc.nextInt();
		map[a][b] = 1;
		map[b][a] = 1;
	}
	
	int K = 1;
	
	for(int i=1; i<=N; i++){
		if(v[i] == 0){
			m.DFS(i, K);
			
			K = K + 1;
		}
	}
	
	
	
	for(int i=1; i<=N; i++){

		bmax[i] = m.BFS(i); 
		
	}
	
	int mv = 987654321;

	
	for(int j=1; j<K; j++){
		mv = 987654321;
		
		for(int i=1; i<=N; i++){
			if(v[i] == j){
				if(bmax[i] < mv){
					mv = bmax[i];
					max[j] = i;
				}
			}
		}

	}
	
	System.out.println(K-1);
	
	for(int i=1; i<K; i++){
		System.out.println(max[i]);
	}
	
	sc.close();
	
	}

}

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

문제

문제

출처

ICPC

어느 부분에서 틀리는 지 모르겠습니다..

hswsua 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말