[코딩테스트] 백준(BAEKJOON) - 이분 그래프(Java, 1707번)

안녕하세요~

 

정말 날씨가 무덥네요... 이제 7월 시작인데 벌써 이러면 어떻게 할지🤣🤣

다들 더위 조심하시기 바랍니다.

 

오늘 풀어볼 문제는 이분 그래프라는 DFS관련 문제입니다.

 

이 문제는 사실 쉬운줄 알았다가 무려 3시간 가까이나 쓰고 결국 질문을 통해서 해결한 문제입니다.

 

이런문제는 또?! 기록을 참을 수 없기에 이렇게 글로 남깁니다.

 

바로 문제링크 남겨드립니다.

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

이분 그래프라는 개념을 몰라서 인터넷으로 검색 후 문제를 풀어봤습니다.

머릿속으로는 아뭐야 껌이네~ 했었습니다.

 

자 다음은 코드와 함께 제 생각을 적어내 보겠습니다.

 

import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	static int m;
	static ArrayList<Integer>[] a;
	static int [] color;
	static boolean checker;
	public static void main(String[] args)  {
		Scanner sc=new Scanner(System.in);
		
		int t=sc.nextInt();
		String[] answer=new String[t];
		for(int time=0;time<t;time++)
		{
			checker=true;
			m=sc.nextInt();
			int n=sc.nextInt();
			a=new ArrayList[m+1];
			
			color=new int[m+1];
			for(int i=1;i<=m;i++)
				a[i]=new ArrayList<>();
			
			
			for(int j=0;j<n;j++)
			{
				int x=sc.nextInt();
				int y=sc.nextInt();
				
				a[x].add(y);
				a[y].add(x);
			}
			
			for(int i=1;i<=m;i++)
			{
				if(color[i]==0)
				{
					color[i]=1;
					dfs(i);
				}
				
			}

			
			if(checker)
				answer[time]="YES";
				
			else
				answer[time]="NO";			
		}
		
		for(int i=0;i<t;i++)
		{
			System.out.println(answer[i]);
		}	
	}
	
	static void dfs(int index)
	{
		for(int i=0;i<a[index].size();i++)
		{
			
			if(color[a[index].get(i)]!=0)
			{
				if(color[index]==color[a[index].get(i)])
				{
					checker=false;
					return;
				}
			}
			else
			{
				if(color[index]==1)
					color[a[index].get(i)]=-1;
				else
					color[a[index].get(i)]=1;
				
				dfs(a[index].get(i));
			}
		}
	}
}

 

이제 문제 풀이에 대한 순서를 작성해 보겠습니다.

① 문제에 필요한 조건(테스트 반복횟수, arr 사이즈, 연관관계)를 받아 설정한다.

- 제가 문제를 풀면서 계속 발생했던 오류는 바로 시간초과 오류였습니다. (저는 arr를 만들때 처음에는 int[][]로 만들었습니다.) 

- 배열문제인지도 모르고 다른 로직만 계속 수정했었네요.😒😒

- 고수님의 답변으로는 해당 문제에 2차원 행렬을 사용한다면 200,000^2의 공간을 사용하기에 공간낭비가 심하다고 합니다.

- 그렇기에 ArrayList를 사용하라고 합니다.

- 그렇습니다 해당 부분을 조금만 생각해본다면 저는 1~200개의 공간을 사용하는데 1~200중 한 개만 연관관계로 이어져 있다면 

② 다음은 주어진 값을 입력받고 이제 DFS탐색을 시작합니다.

③ 우리가 사용할 색깔은 총 두가지 -1, 1입니다.

- 만약 내가 1을 칠했다면 나와 연결돼 있는 요소가 색이 없다면 -1을 칠합니다.

- 근데 내가 1이고 연결돼 있는 요소가 색이 있는데 1이다? 그렇다면 이분 그래프가 아니게 되는것이죠~

- 그렇기 때문에 저는 현재 Index와 연결되는 요소의 색이 같은지 비교하는 로직을 넣었습니다.

- Checker를 통해서 결과값을 출력했습니다.

 

네~ 이번문제는 사실 이틀에 걸쳐서 작성하다보니 뭔가 뒤로갈수록 설명이 간결해지는 듯 하지만...

사실 뭐가 더 있지도 않습니다 헤헤

 

그렇기에 오늘은 여기서 간단하게 마무리하고 다음에 문제를 또 작성해 보겠습니다.

다행히도 오늘은 비가 오지 않았습니다.

 

편안한밤 되시길 바랍니다.

 

감사합니다. :D