백준알고리즘 - 2606_바이러스

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

문제 설명
무조건 1번 컴퓨터와 연결된 컴퓨터들을 찾는 문제이다.

풀이
network 객체는 n번째 PC에 연결된 PC들을 담기 위한 객체이다.
맨 처음엔 network를 이중리스트 구조로 선언하려 했으나, 푸는 도중에 중복되는 값이 들어가면 안 될거 같아서 Set으로 바꿔주었다.

List<Set<Integer>> network = new ArrayList<>();

우선 첫번째 입력으로 주어지는 'PC 갯수'만큼 network 객체를 초기화한다.

for(int i = 0; i <= pcNum; i++) {
	network.add(new HashSet<Integer>());
}

그 다음, 서로 연결된 'pc들의 쌍'이 입력되면 차례대로 network에 값을 넣어주었다. pc들은 서로 연결되어 있으므로 a, b 양쪽에 넣어주었다.

for(int j = 0; j < pairNum; j++) {
	int a = sc.nextInt();
	int b = sc.nextInt();
	network.get(a).add(b);
	network.get(b).add(a);
}

그 다음, 재귀함수를 호출하여 서로 연결된 pc들로 타고 들어가야 한다.
하지만 만약 1번 PC - 2번, 3번, 4번 이 연결되어 있다 치면!

맨 처음에 2번 PC로 재귀함수를 호출할텐데, 그러면 2번 역시 1번 PC와 연결되어 있기 때문에 1번PC가 중복 호출이 된다.
이를 막기 위해 callStack 객체를 사용해주었다.

List<Integer> callStack = new ArrayList<>();

때문에 재귀함수를 처음 호출하기 전에 callStack에 '1'을 쌓아준다.
왜냐면 무조건 1번 PC에서부터 시작하는 거니까.

재귀함수인 "countVirus(x, y)" 에서 'x'는 호출되는 PC이다. 'y'는 호출된 해당 함수에서 새롭게 갱신된 callStack이다.

callStack.add(1);
countVirus(1, callStack); //재귀함수 호출

함수가 호출되자마자 일단 무조건 바이러스 수를 count 해준다.

numberOfVirus++;

그리고 호출된 PC (callCom) 과 연결된 컴퓨터를 iter 객체에 담아준다. 왜 Iterator를 썼냐면 Set 에는 값을 꺼낼 수 있는 함수가 없기 때문이다. 따라서 Iterator를 사용해서 값을 꺼내와야 한다.

Iterator<Integer> iter = network.get(callCom).iterator();

그리고 while문을 돌려 iter 객체에 요소가 있다면 반복하게 해준다.

while(iter.hasNext()) {

computer 에 iter에 담겨있는 요소를 차례대로 하나씩 담는다.

int computer = iter.next();

그리고 callStack 만큼 for문을 돌려 callStack내에 있는 모든 요소 중에 현재 호출된 PC가 있는지 확인한다.

만약 같은 PC가 있다면 중복 체크를 하는 duplication에 true를 넣어주고 반복문을 빠져나온다.

for(int i = 0; i < callStack.size(); i++) {
	if(computer == callStack.get(i)) {
		duplication = true;
		break;
	}
}

만약 현재 호출된 PC가 callStack에 없다면 (중복이 아니라면), 호출된 PC에 연결된 또다른 PC를 검사하기 위해 다시 한 번 재귀함수를 호출하게 된다.

단, 호출하기 전엔 callStack에 해당 PC를 넣어줘야 한다.

if(!duplication) {
	callStack.add(computer);
	countVirus(computer, callStack);
}

전체 코드

	public class Practice2 {
	static int pcNum = 0;
	static int pairNum = 0;
	static List<Set<Integer>> network = new ArrayList<>();
	static int numberOfVirus = -1;
	
	public static void main(String[] args) {
		input();
		System.out.println(solution());
	}
	
	private static void input() {
		Scanner sc = new Scanner(System.in);
		
		// 전역변수에 값 할당
		pcNum = sc.nextInt(); // PC의 총 갯수, 2 ~ 100개
		pairNum = sc.nextInt(); // 연결된 간선의 갯수
		
		for(int i = 0; i <= pcNum; i++) {
			network.add(new HashSet<Integer>());
		}
		
		for(int j = 0; j < pairNum; j++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			
			network.get(a).add(b);
			network.get(b).add(a);
		}
	}

	private static int solution() {
		//1번 컴퓨터가 감염됐을때, 1번때메 감염되는 컴퓨터의 수 출력
		List<Integer> callStack = new ArrayList<>();
		
		callStack.add(1);
		countVirus(1, callStack); //호출해야할 컴퓨터, callStack
		
		return numberOfVirus;
	}

	private static void countVirus(int callCom, List<Integer> callStack) {
		numberOfVirus++;
		Iterator<Integer> iter = network.get(callCom).iterator();
		
		while(iter.hasNext()) {
			int computer = iter.next();
			
			//서로 같은 것은 검사하지 않는다.
			boolean duplication = false;
			for(int i = 0; i < callStack.size(); i++) {
				if(computer == callStack.get(i)) {
					duplication = true;
					break;
				}
			}
			
			//중복이 아니면 재귀함수 호출
			if(!duplication) {
				callStack.add(computer);
				countVirus(computer, callStack);
			}
		}
	}
}

Git gist 주소
https://gist.github.com/ysyS2ysy/c0f08f01755733607b44727e8eb69a0b