백준_상근이의 여행_9372

//알고리즘

1. 그래프 탐색

 -> 주어진 자료로 리스트를 만들어 탐색하여 모든 노드를 거쳐가는 최소값을 구함.

 

방법 1.

import java.util.ArrayList;
import java.util.Scanner;

public class 상근이의여행_9372 {
	static int T, N, M, cnt, ans;
	static boolean v[];
	static ArrayList<Integer>[] list;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		T = sc.nextInt();
		
		for (int tc = 1; tc <= T; tc++) {
			
			N = sc.nextInt();
			M = sc.nextInt();
			v = new boolean[N+1];
			cnt = 0;
			ans = 0;
			
			list = new ArrayList[N+1];
			
			for (int i = 0; i <= N; i++) {
				list[i] = new ArrayList<Integer>();
			}
			
			int start, end;
			for (int i = 0; i < M; i++) {
				start = sc.nextInt();
				end = sc.nextInt();
				
				list[start].add(end);
				list[end].add(start);
			}
			
			dfs(1);
			System.out.println(N-1);
			
		}

	}
	
	private static void dfs(int idx) {
		cnt++;
		if(cnt == N) {
			return;
		}
		v[idx] = true;
		
		for (int i = 0; i < list[idx].size(); i++) {
			if(!v[list[idx].get(i)]) {
				v[list[idx].get(i)] = true;
				ans++;
				dfs(list[idx].get(i));
			}
			
		}
		
	}

}

 

방법 2.

최소 스패닝 트리에서 간선은 N(정점)-1 이므로 대충 입력받고 N-1값 출력해주면 됨.

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

public class 상근이의여행_9372 {
	static int T, N, M;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());

			int start, end;
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				start = Integer.parseInt(st.nextToken());
				end = Integer.parseInt(st.nextToken());
			}

			System.out.println(N - 1);

		}

	}


}