[백준(Baekjoon)][자바(java)] 9372 : 상근이의 여행 / 최소 신장 트리

 

www.acmicpc.net/problem/9372

9372번: 상근이의 여행

 

문제 풀이

 

▶  BFS

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

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		int t = Integer.parseInt( br.readLine() ), n, m, a, b, c, i, u, v;
		boolean e[][], s[];
		Deque<Integer> q;
		while( t-- > 0 ) {
			st = new StringTokenizer( br.readLine() );
			n = Integer.parseInt( st.nextToken() );
			m = Integer.parseInt( st.nextToken() );
			e = new boolean[n][n];
			for( i = 0; i < m; i++ ) {
				st = new StringTokenizer( br.readLine() );
				a = Integer.parseInt( st.nextToken() ) - 1;
				b = Integer.parseInt( st.nextToken() ) - 1;
				e[a][b] = e[b][a] = true;
			}
			c = 0;
			s = new boolean[n];
			q = new LinkedList<>();
			s[0] = true;
			q.add( 0 );
			while( !q.isEmpty()) {
				if( c == n )
					break;
				u = q.remove();
				for( v = 0; v < n; v++ ) {
					if( e[u][v] && !s[v] ) {
						s[v] = true;
						c++;
						q.add( v );
					}
				}
			}
			sb.append( c + "\n" );
		}
		br.close();
		System.out.println( sb.toString() );
        
 	}
}

 

▶  최소 스패닝 트리의 성질을 이용 ( 간선의 개수는 정점의 개수 - 1 이다 )

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

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		int t = Integer.parseInt( br.readLine() ), n, m, a, b, i;
		while( t-- > 0 ) {
			st = new StringTokenizer( br.readLine() );
			n = Integer.parseInt( st.nextToken() );
			m = Integer.parseInt( st.nextToken() );
			for( i = 0; i < m; i++ )
				br.readLine();
			sb.append( (n-1) + "\n" );
		}
		br.close();
		System.out.println( sb.toString() );
        
 	}
}