[백준] 2606번 - 바이러스

 

대표사진 삭제

• 사진 편집
•  
• 작게작게문서 너비문서 너비옆트임옆트임
•  
• 삭제삭제

사진 설명을 입력하세요.

대표사진 삭제

사진 설명을 입력하세요.

우선탐색 문제이다. 이차원 배열에 그래프를 표현해주기 위해서 노드 a, b 의 연결을 ary[a][b]와 ary[b][a]로 모두 표현해주었고, 방문했을 때 visited배열의 값을 바꾸어주어서 해결하였다.

여태까지 bfs, dfs에 대해서 조금은 헤매면서 풀이를 찾아서 해결했었는데 조금씩 스스로의 힘으로 풀게되는 것 같다.

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 p2606 {
	static int[][] ary;
	static boolean[] visited;
	static int a;
	static int b;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		a = Integer.parseInt(br.readLine());
		b = Integer.parseInt(br.readLine());

		ary = new int[a + 1][a + 1];
		visited = new boolean[a + 1];
		visited[1] = true;
		for (int i = 0; i < b; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			ary[x][y] = 1;
			ary[y][x] = 1;
		}
		bfs(1);
	}

	public static void bfs(int start) {
		Queue<Integer> q = new LinkedList<>();
		int cnt = 0;
		q.add(start);

		while (!q.isEmpty()) {
			int n = q.poll();
			for (int i = 1; i <= a; i++) {
				if (ary[n][i] == 1 && visited[i] == false) {
					q.add(i);
					visited[i] = true;
					cnt++;
				}
			}
		}
		System.out.println(cnt);
	}
}