[백준 BOJ] 2606번 바이러스 (Java)

문제 설명

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

2606번: 바이러스

 

접근 방법 - 큐를 이용한 너비 우선 탐색 (BFS)

백준의 2606번 문제는 깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS)으로 해결해야 하는 문제이다.

필자의 경우에는 큐를 이용하여 BFS 알고리즘을 사용하였는데 DFS 알고리즘을 이용해도 무관할 것이다.

해당 문제에선, 주어진 컴퓨터 네트워크에 대하여 1번 컴퓨터가 감염되었다고 가정하였을 시 몇 대의 컴퓨터가 감염되었을지에 대한 해답을 묻고 있다.

필자는 이에 대해서, 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

큐를 어떻게 사용하였는지, BFS 알고리즘은 어떻게 이용하였는지에 대한 내용은 아래를 참고하길 바란다.

 

필자는 여기서 배열을 별도로 사용하는데, 아래의 규칙을 정해두고 배열의 값을 바꾸었다.

0 : 바이러스 감염되지 않음

1 : 바이러스 감염됨

 

코드의 실행 순서

1) 문제에서 제시하는 입력값을 모두 입력받는다.

(컴퓨터의 개수 n1, 네트워크 연결망의 개수 n2, 네트워크로 연결되어있는 컴퓨터들의 쌍 x[] - y[] )

 

2) 1)에서 입력받을 때, 바이러스 감염 여부를 나타내는 배열 a[]를 선언한다.

그리고 a[]의 모든 배열값을 0으로 초기화하고, a[1]의 값을 1로 바꾼다. (1번 컴퓨터 감염)

(여기서 배열의 크기를 원래 크기에 1 더하여 선언한다. 컴퓨터 번호의 시작은 0번이 아니라 1번이다.)

 

3) 큐를 선언하고, 가장 먼저 감염된 컴퓨터 1을 큐에 푸시한다.

 

4) 반복문을 실행한다.

(여기서 count 변수는 바이러스에 감염된 컴퓨터 개수이다.)

- x[i]가 큐의 front 값과 같고 x[i]와 쌍을 이루는 y[i] 컴퓨터가 감염되지 않았다면, y[i]를 감염시키고 큐에 푸시한다. 그리고 count에 1을 더한다.

- y[i]가 큐의 front 값과 같고 y[i]와 쌍을 이루는 x[i] 컴퓨터가 감염되지 않았다면, x[i]를 감염시키고 큐에 푸시한다. 그리고 count에 1을 더한다.

- 반복문을 한번 실행할 때마다 큐의 front 값을 반환한다.

=> 큐가 완전히 비게 될 때까지 위 과정을 반복한다.

 

5) 연산이 끝나면 최종적으로 저장된 count 값을 출력하고 실행 종료한다.

 

후기

지금 보면 코드 자체는 깔끔하게 작성되었고, 큐와 BFS 알고리즘 또한 적절하게 사용한 것으로 보인다.

다만 제출 결과를 보면 메모리도 시간도 너무 많이 사용된 것으로 나타난다.

아마 Java로 코딩을 진행해서 그런 것이라 판단된다. (실제로 ps를 Java로 하는 경우는 잘 없다.)

Java 사용법을 익히는 것도 중요하긴 하지만, ps를 할 때엔 되도록 Java 이외의 언어를 사용하는 것이 수월할 것이라 생각하였다.

반응형

 

성공한 코드

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

//백준 2606번 코드
public class Main {
	public static void main(String args[]) {
		Scanner s=new Scanner(System.in);
		int n1=s.nextInt();//컴퓨터 개수
		int a[]=new int[n1+1];//컴퓨터 배열(0:감염x/1:감염o)
		int n2=s.nextInt();//묶여진 쌍 개수
		int x[]=new int[n2];
		int y[]=new int[n2];
		for(int i=0;i<n2;i++) {//연결된 쌍 정보 입력받기
			x[i]=s.nextInt();
			y[i]=s.nextInt();
		}
		
		for(int i=1;i<n1+1;i++) {//1번 컴퓨터에 바이러스 넣기
			a[i]=0;
		}
		a[1]=1;
		
		//탐색과정
		int count=0;
		Queue<Integer> q=new LinkedList<Integer>();
		q.add(1);
		while(!q.isEmpty()) {
			for(int i=0;i<n2;i++) {
				if(x[i]==q.peek()&&a[y[i]]==0) {
					a[y[i]]=1;
					q.add(y[i]);
					count++;
				}
				else if(y[i]==q.peek()&&a[x[i]]==0) {
					a[x[i]]=1;
					q.add(x[i]);
					count++;
				}
			}
			q.poll();
		}
		System.out.println(count);
	}
}

 

제출 결과

(2020.01.25 백준 2606번 문제 제출 결과)

(메모리 초과 쉽게 볼 수 없는 결과인데...)