글 읽기 - (Java)이분그래프 어디가 틀린걸까요???ㅠㅠ

gkqrur 7년 전 0

질문게시판에 올려주신 테스트케이스도 다 돌려봤는데 어디서 틀린건지 모르겠어요ㅜㅜ

제가 풀이한 방법은 일단 인접리스트에 그래프와 dfs를 이용했습니다.

check배열은 방문여부를 체크하고, 해당 정점이 어떤 쪽(team)에 속하는지를 구분했습니다.

check[]값이 0일때는 방문아직 안한거, 1일때는 방문했고 정점이 team1에 속하는 것, 2일때는 방문했고 정점이 team2에 속하는 것입니다.

dfs()부분에서 for문을 돌때 자기랑 연결된 정점들이 check[]가 0이 아닐때, 자신과 같은 team(check[])값을 가지고 있으면

boolean b를 false로 바꾸고 return 했습니다.

어디가 잘못된걸까요???

도와주세요... 부탁드립니다ㅜㅜ

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static ArrayList<Integer>[] arr;
	static int[] check; //방문x : 0 , 방문o && team1 : 1, 방문o && team2 : 2
	static boolean b = true;
	
    //dfs
    static void dfs(int s){
        
		for(int i = 0; i<arr[s].size();i++){
			int temp = arr[s].get(i);//s와 연결된 정점을 temp에 저장
			if(check[temp] == 0){//temp가 아직 방문되지 않았을 때
				if(check[s] == 1)
					check[temp] = 2;
				else
					check[temp] =1;
				dfs(temp);//재귀
			}else{//temp가 방문되었을 때
				if(check[s] == check[temp]){//s와 연결된 temp가 서로 같은 팀일때 이분그래프가 아니므로
					b = false;            //b를 false로 변경한 후 retrun;
					return;
				}
			}
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int tc = sc.nextInt();
		
		while(tc-->0){
			int vNum = sc.nextInt();//정점개수
			int eNum = sc.nextInt();//간선개수
			
			arr = (ArrayList<Integer>[])new ArrayList[vNum+1];
			check = new int[vNum+1];
			
			for(int i = 1;i<=vNum;i++)
				arr[i] = new ArrayList<Integer>();
			
			for(int i = 1;i<=eNum;i++){ //그래프 저장
				int x = sc.nextInt();
				int y = sc.nextInt();
				
				arr[x].add(y);
				arr[y].add(x);
				
				
			}
			
            //연결요소가 2개이상일 경우(끊어진 경우)까지 다 탐색하기 위해서 for문으로 dfs()호출
			for(int i = 1; i<=vNum;i++){
				if(check[i] == 0){
					check[i] = 1;
					dfs(i);
				}
				if(b == false){
					break;
				}
			}
			
			if(b==false)//b가 false이면 이분그래프 아님
				System.out.println("NO");
			else{
				System.out.println("YES");
			}
			
			
			
		}
		
	}
}

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

문제

문제

출처

ICPC

(Java)이분그래프 어디가 틀린걸까요???ㅠㅠ

gkqrur 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말