글 읽기 - 틀렸다고 나오는데 반례나 코드 검토 부탁드립니다!

kjjanggu 5년 전 0

예제는 물론 제가 입력해본 모든 경우에서는 제대로된 출력값이 나옵니다.

하지만 채점을 돌렸을 때는 메로리 초과 혹은 시간 초과가 아닌 틀렸습니다로 나오는데

혹여나 제가 어디서 실수했는지 검토 부탁드립니다!

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/*
 * com 1과 연결된 컴퓨터들의 수 구하기 
 */
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int comNum = sc.nextInt();
		int n = sc.nextInt();
		HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>(); // key 컴퓨터와 연결된 컴퓨터들의 리스트로 구성된 맵
		HashSet<Integer> keySet = new HashSet<Integer>(); // 컴퓨터 재 탐색 방지; 무한루프 방지
		HashSet<Integer> valueSet = new HashSet<Integer>(); // 한 컴퓨터는 다른 하나의 컴퓨터로부터 연결되어짐.
		Queue<Integer> queue = new LinkedList<Integer>();
		
		for(int i=0; i<n; i++) {
			int _key = sc.nextInt();
			int _value = sc.nextInt();
			if(!valueSet.contains(_value)) {
				if(map.get(_key)==null) 
					map.put(_key, new ArrayList<Integer>());
				map.get(_key).add(_value);
				valueSet.add(_value);
			}
		}
		
		int cnt = -1;
		queue.offer(1); // 컴퓨터 1부터 시작
		while(queue.size()>0) {
			int _now = queue.poll();
			if(!keySet.contains(_now)) {
				keySet.add(_now);
				ArrayList<Integer> valueList = map.get(_now);
				if(valueList !=null) {
					for(int i=0; i<valueList.size(); i++) {
						queue.offer(valueList.get(i));
					}
				}
				cnt++;	
			}
		}
		System.out.println(cnt);
	}
}

djm03178 5년 전 1

2 3

1 3

2가 나와야 하는데 0이 나옵니다.

1 3

2 3

이것도 2가 나와야 하지만 1이 나옵니다.

kjjanggu 5년 전 0

반례 지적 감사합니다!

제가 양방향 그래프를 잘 못 설정했었습니다.

덕분에 해결했습니다! 좋은 하루 보내세요~

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/*
 * com 1과 연결된 컴퓨터들의 수 구하기 
 */
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int comNum = sc.nextInt();
		int n = sc.nextInt();
		HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>(); // key 컴퓨터와 연결된 컴퓨터들의 리스트로 구성된 맵
		HashSet<Integer> keySet = new HashSet<Integer>(); // 중복된 컴퓨터 탐색 방지; 무한루프 방지
		Queue<Integer> queue = new LinkedList<Integer>();
		
		for(int i=0; i<n; i++) {
			int _key = sc.nextInt();
			int _value = sc.nextInt();
			if(map.get(_key)==null) 
				map.put(_key, new ArrayList<Integer>());
			if(!map.get(_key).contains(_value))
				map.get(_key).add(_value);
			// 양방향 그래프
			if(map.get(_value)==null) 
				map.put(_value, new ArrayList<Integer>());
			if(!map.get(_value).contains(_key))
				map.get(_value).add(_key);
			
		}
		
		int cnt = -1;
		queue.offer(1); // 컴퓨터 1부터 시작
		while(queue.size()>0) {
			int _now = queue.poll();
			if(!keySet.contains(_now)) {
				keySet.add(_now);
				ArrayList<Integer> valueList = map.get(_now);
				if(valueList !=null) {
					for(int i=0; i<valueList.size(); i++) {
						queue.offer(valueList.get(i));
					}
				}
				cnt++;	
			}
		}
		System.out.println(cnt);
	}
}

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

문제

문제

출처

ICPC

틀렸다고 나오는데 반례나 코드 검토 부탁드립니다!

kjjanggu 5년 전 0

djm03178 5년 전 1

kjjanggu 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말