글 읽기 - [Java_바이러스] 반례를 찾았습니다 그런데...

swkim20kr 5년 전 0

제목대로 반례를 찾았습니다.

1 3

4 5

3 2

이 반례를 찾았는데 이것에 대한 정답은 2가 나와야 정상인거 아닌가요? (반례의 답은 3이라고 하더군요)

출력) 1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

이 말에 의하면, 1번 컴퓨터가 감염일 때는 2개가 되는 것이고, 4번 컴퓨터가 감염일 때는 1개가 되는 것인데

왜 3인지 모르겠네요 반례가 잘못된건가...

예제에도 보면 1번 컴퓨터는 포함을 시키고 있지 않는 거 같거든요?

1번이 감염시킨 컴퓨터의 개수를 구하는 것이기 때문에 그런거 같은데 아닌가요?

여기서 질문!! 그렇다면 왜 틀렸을까요? ㅜㅜ

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int computer = in.nextInt(); // 컴퓨터 수
		int connect_line = in.nextInt(); // 컴퓨터의 연결선 수
		Set<Integer> stack = new HashSet<>(); // 연결 대상이 되는 컴퓨터들을 모은 Set
		List<ArrayList<Integer>> link_list = new LinkedList<>(); // 감염된 컴퓨터들과 연결되어 있지 않은 컴퓨터

		if (computer <= 100) { // 컴퓨터의 수는 100 이하의 수만 가능
			for (int i = 0; i < connect_line; i++) {
				// 컴퓨터 번호 쌍 a,b 입력
				int a = in.nextInt(); // a
				int b = in.nextInt(); // b

				if (stack.isEmpty()) { // 맨 처음 공간이 비어있으므로, 처음에 들어온 값은 무조건 삽입
					stack.add(a);
					stack.add(b);
				} else {
					if (stack.contains(a) || stack.contains(b)) { // stack에 존재하는 값이 있다면?
						if (link_list.isEmpty()) { // 감염되지 않은 컴퓨터들에 대해 조사
							stack.add(a);
							stack.add(b);
						} else { // 감염되지 않은 컴퓨터들이 존재하면 
							for (int d = 0; d < link_list.size(); d++) {
								boolean bb = false; // 입력한 컴퓨터 a,b와 격리된 컴퓨터 비교
								int select = 0;
								for (int f = 0; f < link_list.get(d).size(); f++) {
									int g = link_list.get(d).get(f);
                                    // 만약 a,b와 격리된 컴퓨터가 일치하는 게 있다면 
                                    // 처음엔 격리 시켰지만, 차후에 감염된 컴퓨터임을 확인
									if (a == g || b == g) {
										select = d;
										bb = true;
									} else {
										stack.add(a);
										stack.add(b);
									}
								}
								if (bb == true) {
									for(int u=0;u<link_list.get(select).size();u++) {
										stack.add(link_list.get(select).get(u)); // 차후에 감염된 컴퓨터들에 대해 stack 삽입
									}
									link_list.remove(select); // 차후에 감염된 컴퓨터 list에서 제거
								}
							}
						}
					}else { // Stack과 비교해서 일치하는 게 없다면 이는 격리된 컴퓨터임을 확인
						ArrayList<Integer> arr_list = new ArrayList<>();
						arr_list.add(a);
						arr_list.add(b);
						link_list.add(arr_list);
					}
				}
			}
			System.out.println(stack.size()-1);
		}else {
			System.out.println("100을 초과하는 컴퓨터 수");
		}
	}
}

jh05013 5년 전 0

저건 2가 맞습니다.

swkim20kr 5년 전 0

제가 맞는거죠? ㅋㅋ 순간 "나만 이해 못하는 문제인가?" 싶었네요 ㅋㅋㅋ;

답변 고맙습니다 jh05013님~

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[Java_바이러스] 반례를 찾았습니다 그런데...

swkim20kr 5년 전 0

jh05013 5년 전 0

swkim20kr 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말