백준_9372 상근이의 여행(자바) / BFS

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.Back;

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

public class Back_9372 {
	static int N,M,ans;
	static boolean visited[];
	static int[][] arr;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int testCase = Integer.parseInt(br.readLine());
		StringTokenizer st;
		
		for (int tc = 0; tc < testCase; tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			ans = 0;
			
			arr = new int[N+1][N+1];
			visited = new boolean[N+1];
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				
				arr[a][b]=1;
				arr[b][a]=1;
			}
			
			bfs();
			sb.append(ans-1+"\n");
		}
		System.out.println(sb);
	}

	private static void bfs() {
		Queue<Integer> q = new LinkedList<>();
		q.add(1);
		visited[1]=true;
		while(!q.isEmpty()) {
			ans++;
			int tmp = q.poll();
			for (int i = 1; i <= N; i++) {
				if(arr[tmp][i]!=0 && !visited[i]) {
					visited[i]=true;
					q.add(i);
				}
			}
		}
	}
}

- 이 문제는 트리 문제를 풀고 싶어서 접근을 했습니다. 그런데 그래프 탐색에 좀 더 가깝게 풀 수 있는 문제였던 거 같습니다.

 

- BFS 문제 풀이 처럼 배열을 만들어 주고 방문처리를 진행해주면서 문제를 해결하면 됩니다.

 

- 크게 특이사항이 없었던 문제였습니다...