글 읽기 - 다소.. 풀이가 엉성한것 같습니다...

vegetable 5년 전 1

아래 알려주신 내용을 토대로 순서에 상관없이 양방향 그래프로 처리하였습니다만..

틀리네요.. 엄청나게 에러로그를 쏟아내고 나니 지쳐서 정답을 보았지만.. 식견이 부족하여 이해가 가지 않네요ㅠㅠ..

다른분들의 소스로 돌려본 테스트케이스로는 같은 결과값을 내고있는데 어떤부분을 놓치고있는지

도통 감이 오지 않아 고수분들의 도움을 구하고자 합니다ㅠ

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

class P {
	public int x, y;

	public P(int x, int y) {
		this.x = x;
		this.y = y;
	}
}
public class Main{
	static int n, m, p;
	static ArrayList<Integer>[] res;
	static boolean[] knows;
	static int[][] list;
	static boolean[][] isVisit;

	public static void main(String[] args)throws Exception {
		Scanner s = new Scanner(System.in);
		n = s.nextInt();// 사람 수
		m = s.nextInt();// 파티 수
		p = s.nextInt();// 진실을 아는 사람의 수
		knows = new boolean[51];
		list = new int[51][51];
		
		//파티 수 만큼 저장
		res = (ArrayList<Integer>[]) new ArrayList[m];
		for(int i =0; i< m; i++){
			res[i] = new ArrayList<Integer>();
		}
		
		//진실을 아는사람 저장
		for (int i = 0; i < p; i++) {
			int t = s.nextInt();
			knows[t] = true;
		}
		
		
		for (int i = 0; i < m; i++) {
			int person = s.nextInt();
			if(person==0) { // 0일때 0으로 채워줌, 결과값에 +1 영향을 주도록
				res[i].add(0);
				list[0][0] = 1;
			}else {
				for (int j = 0; j < person; j++) {
					int t = s.nextInt();
					res[i].add(t);
				}
			}
		}
		
		//행렬처리
		for(int i =0; i< res.length;i++) {
			if(res[i].size()>0) {
				for(int j=0;j<res[i].size()-1;j++) {
					int a = res[i].get(j);
					int b = res[i].get(j+1);
					list[a][b] = 1;
					list[b][a] = 1;
				}
			}
		}
		
	
		//0부터 탐색
		for (int i = 0; i <= n; i++) {
			bfs(i);
		}
		
		int knowCnt = 0;//진실을 모르는사람의 수
		for (int i = 0; i <= n; i++) { 
			if (knows[i] == false) { 
				knowCnt++;
			}
		}

        //---------예상 오류지점----------
		int temp = 0;//결과값을 저장
		for (int i = 0; i < m; i++) { // 파티수만큼 반복
			boolean b = true; // 아래 예외에 걸리지 않으면 temp를 증가시키기 위한 변수
			if (knowCnt > 0) {//진실을 모르는사람이 존재하면
				for(int j = 0; j < res[i].size(); j++){ //처음 입력받은 배열을 돌면서
					if(knows[res[i].get(j)]==true){//진실을 아는사람이 한명이라도 있다면 b를 false처리
						b = false;
					}
				}
				if(b==true) ++temp;
			}
		}

		System.out.println(temp);
		s.close();
	}

	static void bfs(int start) {
		isVisit = new boolean[n+1][n+1];
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(start);

		while (!q.isEmpty()) {
			int s = q.poll();
			for (int i = 0; i < n; i++) {
				if (list[s][i] == 1 && !isVisit[s][i]) {
					if (knows[i]) knows[s] = true;
					isVisit[s][i] = true;
					q.add(i);
				}
			}
		}
	}
}
/*
4 4
1 1
2 1 2
1 3
2 3 4
0 0
(답 3)

4 4
1 1
2 3 2
3 4 1 3
2 4 1
0 0
(답 1)

3 2
1 1
2 2 3
2 1 2
(답 0)
*/

djm03178 5년 전 4

코드가 복잡해서 분석해드리긴 어렵지만, 대신 반례들을 제공해 드립니다.

4
1 3
2 3
2
3
1 3
output: 1
correct answer: 0

4
3
3
2
1 3
2 3
output: 1
correct answer: 0

3
4
1 3 4
1
1 2 3 4
output: 1
correct answer: 0

vegetable 5년 전 0

와 댓글 달아주신 반례들로 데이터 검증 후 런타임 에러 잡았더니 풀었습니다 ㅠㅠ

도와주신 rkn04, djm03178님 감사합니다

건승하세요!!

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

문제

문제

출처

ICPC

다소.. 풀이가 엉성한것 같습니다...

vegetable 5년 전 1

djm03178 5년 전 4

vegetable 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말