40. 2606번 바이러스

https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

바로전에 포스팅한 문제와 동일한 그래프 문제

DFS를 이용해 해결했다

 

고려해야할 점은

1. 서로 선으로 연결되어 있다는점

2. 때문에 1~2와 2~1은 같다고 처리해주어야한다는 것

 

1. 입력부분

public static void main(String[] args) throws IOException,NumberFormatException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		n = Integer.parseInt(br.readLine());
		m = Integer.parseInt(br.readLine());
		
		map = new int[n+1][n+1]; //탐색 경로 저장
		visited = new boolean[n+1]; //탐색확인
		
		for(int i=0; i<m; i++){
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			map[a][b] = map[b][a] = 1;
			//둘은 같은 경우의수
		}

		dfs(1);
        //1부터 탐색 시작

		System.out.println(cnt);
		
	}

 

2. 탐색 부분

public static void dfs(int x) {	
		visited[x] = true;

		for(int y=0; y<=n; y++){ //y<n 이 아니다 y<=n 이다
			if(map[x][y]==1 && !visited[y]) {
				cnt++;
				dfs(y);
			}
		}		
	}

 

결과