백준 - 1707번 - 이분 그래프

1707번

#1 메모리초과된 내 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static boolean[][] graph;
	static int[] check;

	static Queue<Integer> queue = new LinkedList<>();

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(bf.readLine());



		for (int i = 0; i<num; i++) {
			StringTokenizer st  = new StringTokenizer(bf.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			graph = new boolean[A+1][A+1];
			check = new int[A+1];
			for (int j = 0; j<B; j++) {
				StringTokenizer st2 = new StringTokenizer(bf.readLine());
				int N = Integer.parseInt(st2.nextToken());
				int M = Integer.parseInt(st2.nextToken());
				graph[N][M] = graph[M][N] = true;
			}
			sb.append(bfs(A)).append('\n');
//			bfs(A);
//			for (int j = 1; j<check.length; j++) {
//				for (int k = 1; k<3; k++) {
//					System.out.println(j +" "+ k+ " " +check[j][k]);
//				}
//			}
//			String result = "Yes";
//			for (int j = 1; j<check.length; j++) {
//				if (check[j] == 2) {
//					result = "No";
//					break;
//				}
//			}
//			if (result.equals("Yes")) {
//				sb.append(result).append('\n');
//			} else {
//				sb.append("No").append('\n');
//			}
		}
		System.out.print(sb);
	}

	static String bfs(int N) {

		queue.add(N);
		check[N] = 1;

		while (!queue.isEmpty()) {
			N = queue.poll();
			for (int i = 1; i<N+1; i++) {
				if (graph[N][i] && check[i] != 1) {
					queue.add(i);
					check[i] = 1;
				} else if (graph[N][i] && check[i] == 1) {
					check[i] = 2;
					return "NO";
				}
			}
		}
		return "YES";
	}
}

#2 정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int[] check;
	static ArrayList<Integer>[] al;
	static int A, B;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(bf.readLine());

		for (int i = 0; i<num; i++) {
			StringTokenizer st  = new StringTokenizer(bf.readLine());
			A = Integer.parseInt(st.nextToken());
			B = Integer.parseInt(st.nextToken());
			al = new ArrayList[A+1];
			check = new int[A+1];
			
			for (int j = 0; j<=A; j++) {
				al[j] = new ArrayList<Integer>();
			}
			for (int j = 0; j<B; j++) {
				StringTokenizer st2 = new StringTokenizer(bf.readLine());
				int N = Integer.parseInt(st2.nextToken());
				int M = Integer.parseInt(st2.nextToken());
				al[N].add(M);
				al[M].add(N);
			}
			bfs();
		}
	}

	static void bfs() {

        Queue<Integer> queue = new LinkedList<>();
		for (int i = 1; i<=A; i++) {
			if (check[i] == 0) {
				queue.add(i);
				check[i] = 1;
			}
			while (!queue.isEmpty()) {
				int now = queue.poll();
				for (int j = 0; j<al[now].size(); j++) {
					if (check[al[now].get(j)] == 0) {
						queue.add(al[now].get(j));
					}
					if(check[al[now].get(j)] == check[now]) {
						System.out.println("NO");
						return;
					}

					if(check[now] == 1 && check[al[now].get(j)] == 0)
						check[al[now].get(j)] = 2;
					else if(check[now] == 2 && check[al[now].get(j)] == 0)
						check[al[now].get(j)] = 1;
				}
			}
		}
		System.out.println("YES");

	}
}

풀이

---

주어진 수들의 연결이 이분그래프인지 체크하는 문제다.

지금까지 풀어왔던 방식대로 2차원배열로 정점끼리의 연결을 나타내고 정점이 탐색되었는지 확인하는 check배열을 만들어서 진행했다.

bfs메서드를 만들어 탐색되지 않으면 0, 한번 탐색되면 1, 두번 탐색되면 2를 출력하게해 2가나오면 이분그래프가 아니다

그런데 메모리초과가났다.

정답을 보니 ArrayList[]에 new ArrayList를 해서 풀더라 al[N].add(M), check[al[now].get(j)이런 생소한 로직이 나를 반겨줬다. 하지만 뭔가 2차원배열 역할을 대신하는 느낌을 받았다.

List 2차원 배열 만들기

import java.util.*;
public class Arraylist {
    public static void main(String[] args)
    {
        int n = 5;
  
  		// 변수 정의 선언
        ArrayList<Integer>[] al = new ArrayList[n];
  
        // 각 행에 ArrayList 객체를 할당
        for (int i = 0; i < n; i++) {
            al[i] = new ArrayList<Integer>();
        }
  
		// n번째 줄에 선 사람들의 키를 저장한다고 치면..
        al[0].add(170);
        al[0].add(165);
        al[1].add(182);
        al[2].add(193);
        al[2].add(155);
        al[2].add(172);
        al[3].add(162);
        al[4].add(120);
        al[4].add(150);
  
        for (int i = 0; i < n; i++) {
        	List<Integer> line = al[i];
            System.out.print((i+1) + "th line : ");
            for (int j = 0; j < line.size(); j++) {
            	System.out.print(line.get(j) + "cm ");
            }
            System.out.println();
        }
    }
}

출력

이제 #2의 풀이를 보자
ArrayList[] al = new ArrayList[n];
리스트 배열을 선언하고 인덱스 A만큼 또 리스트를 선언한다.
al[i] = new ArrayList();
접점을 나타내는 2차원배열을 구현할때 시작점과 끝점을 배열에 넣어준다.
check[i] == 0이면 큐에 넣고 check[i] = 1로 해준다.

if(check[now] == 1 && check[al[now].get(j)] == 0)
	check[al[now].get(j)] = 2;
else if(check[now] == 2 && check[al[now].get(j)] == 0)
	check[al[now].get(j)] = 1;

정상적인 이분그래프라면 1, 2, 1, 2같이 징검다리처럼 숫자가 부여될것이다. 설령 1, 1, 2, 2 이렇게 나와도

if(check[al[now].get(j)] == check[now]) {
	System.out.println("NO");
	return;
}

위 조건처럼 서로 같은 숫자를 부여 받은 수끼리 연결되어있다면 이분 그래프가 아닌것이다.