글 읽기 - 반례를 못찾겠어요. 바이러스 문제

kim2100 6년 전 0

map 과 set을 이용해서

맵에 연결된 node 들을 키와 자식들로 넣고, 비교하는데 반례를 못찾겠습니다.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class Virus {
	int[] arr = new int[2];
	@SuppressWarnings("rawtypes")
	static Map<Integer, Set> temp_map = new HashMap<Integer, Set>();
	static Set<Integer> set;
	static Set<Integer> resultSet = new HashSet<Integer>();
	static List<Integer> list = new ArrayList<Integer>();
	Object[] Arr;
	private static Scanner sc;

	public void virus(int com) {
		if (com > 100) {
			System.out.println("100 이하의 숫자로 입력해주세요.");
		}
	}

	public Set<Integer> rSet(Map<Integer, Set<Integer>> map, Set<Integer> set) {
		Object[] array = set.toArray();
		for (int a = 0; a < array.length; a++) {
			int iArray = Integer.valueOf(array[a].toString());
			System.out.println(map.get(iArray) + "," + iArray + ",");
			if (map.get(iArray) != null) {
				set.addAll(map.get(iArray));
			}
		}
		return set;
	}

	public Object[] createVirus(Map<Integer, Set<Integer>> map, int node) {
		if (!list.contains(node)) {
			list.add(node);
			Arr = map.get(node).toArray();
			for (int i = 0; i < Arr.length; i++) {
				resultSet.addAll(map.get(Arr[i]));
			}
			for (int j = 0; j < Arr.length; j++) {
				createVirus(map, (int) Arr[j]);
			}
		}
		return Arr;
	}

	public Map<Integer, Set<Integer>> mapCreate(int com, int cnt) {
		List<Integer> temp_list = new ArrayList<Integer>();
		Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
		for (int i = 1; i <= com; i++) {
			map.put(i, null);
		}
		for (int k = 0; k < cnt; k++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			if (a > com || b > com) {
				System.out.println("점이 없습니다.");
				return null;
			} else {
				temp_list.add(a);
				temp_list.add(b);
				temp_list.add(0);
			}
		}
		for (int i = 1; i < temp_list.size() + 1; i++) {
			if (temp_list.contains(i)) {
				set = new HashSet<Integer>();
				for (int k = 0; k < temp_list.size(); k++) {
					if (temp_list.get(k) == i && temp_list.get(k + 1) != 0) {
						set.add(temp_list.get(k + 1));
					}
					if (temp_list.get(k) == i && temp_list.get(k + 1) == 0) {
						set.add(temp_list.get(k - 1));
					}
				}
				map.put(i, set);
			}
		}
		return map;
	}

	public String DFS(Map<Integer, Set<Integer>> map) {
		String dfsStr = null;
		Object[] arrBfs = resultSet.toArray();
		dfsStr = "값은" + map.get(arrBfs[0]);
		for (int i = 1; i < arrBfs.length; i++) {
		}

		return dfsStr;
	}

	public static void main(String[] args) {
		Virus vi = new Virus();
		sc = new Scanner(System.in);
		int com = sc.nextInt();
		vi.virus(com);
		int cnt = sc.nextInt();
		Map<Integer, Set<Integer>> map = vi.mapCreate(com, cnt);
		if (map.get(1) != null) {
			resultSet.addAll(map.get(1));
			vi.createVirus(map, 1);
			// Object[] temp_Arr = vi.createVirus(map, 1);
			// for (int n = 0; n < temp_Arr.length; n++) {
			// vi.createVirus(map, (int) temp_Arr[n]);
			// }
		}

		System.out.println((resultSet.size() - 1));
	}
}

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

문제

문제

출처

ICPC

반례를 못찾겠어요. 바이러스 문제

kim2100 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말