[Python/Java] 백준 1707 - 이분 그래프 [DFS/BFS]

문제

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

 

해설

DFS와 BFS 모두 사용가능한 문제이다. DFS를 이용하는 것이 개인적으로 이번 문제에선 이해가 잘 되었던 것 같다.

 

Python

Python은 파이썬의 기본 재귀 깊이 제한은 1000이기 때문에 setrecursionlimit를 사용하지 않으면 런타임 에러가 발생한다. 너무 크게 설정해도 메모리 오류가 발생하므로 적절한 크기로 조절이 필요하였다.

 

DFS

from sys import stdin, setrecursionlimit
setrecursionlimit(100000)


def dfs(graph: list, visited: list, colors: list, node: int, color: int):
    visited[node] = True
    colors[node] = color

    for neighbor in graph[node]:
        if not visited[neighbor]:
            if not dfs(graph, visited, colors, neighbor, 1 - color):
                return False
        elif colors[neighbor] == colors[node]:
            return False
    return True


def is_bipartite(n: int, graph: list):
    visited = [False] * (n + 1)
    colors = [-1] * (n + 1)

    for i in range(1, n + 1):
        if not visited[i]:
            if not dfs(graph, visited, colors, i, 0):
                return "NO"
    return "YES"


k = int(stdin.readline())
for _ in range(k):
    vertex, edge = map(int, stdin.readline().split(" "))
    adj_list = [[] for _ in range(vertex + 1)]  # 인접 리스트로 변경

    for _ in range(edge):
        u, v = map(int, stdin.readline().split(" "))
        adj_list[u].append(v)
        adj_list[v].append(u)

    print(is_bipartite(vertex, adj_list))

 

BFS

from sys import stdin
from collections import deque


def bfs(graph: list, visited: list, start: int, colors: list):
    queue = deque([start])
    visited[start] = True
    colors[start] = 1

    while queue:
        node = queue.popleft()

        for neighbor in graph[node]:
            if not visited[neighbor]:
                queue.append(neighbor)
                visited[neighbor] = True
                colors[neighbor] = -colors[node]
            elif colors[node] == colors[neighbor]:
                return False
    return True


def is_bipartite(n: int, graph: list):
    visited = [False] * (n+1)
    colors = [-1] * (n+1)

    for i in range(1, n+1):
        if not visited[i]:
            if not bfs(graph, visited, i, colors):
                return "NO"
    return "YES"


k = int(stdin.readline())
for _ in range(k):
    vertex, edge = map(int, stdin.readline().split(" "))
    adj_list = [[] for _ in range(vertex + 1)]  # 인접 리스트로 변경

    for _ in range(edge):
        u, v = map(int, stdin.readline().split(" "))
        adj_list[u].append(v)
        adj_list[v].append(u)

    print(is_bipartite(vertex, adj_list))

 

Java

DFS

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine().trim());

        for (int t = 0; t < k; t++) {
            String[] condition = br.readLine().split(" ");
            int vertex = Integer.parseInt(condition[0]);
            int edge = Integer.parseInt(condition[1]);

            List<Integer>[] adjList = new ArrayList[vertex + 1];
            for (int i = 0; i <= vertex; i++) {
                adjList[i] = new ArrayList<>();
            }

            for (int i = 0; i < edge; i++) {
                String[] edgeInfo = br.readLine().split(" ");
                int u = Integer.parseInt(edgeInfo[0]);
                int v = Integer.parseInt(edgeInfo[1]);

                adjList[u].add(v);
                adjList[v].add(u);
            }

            System.out.println(isBipartite(vertex, adjList) ? "YES" : "NO");
        }
    }

    static boolean dfs(List<Integer>[] graph, int[] colors, int node, int color) {
        colors[node] = color;

        for (int neighbor : graph[node]) {
            if (colors[neighbor] == -1) {
                if (!dfs(graph, colors, neighbor, 1 - color)) {
                    return false;
                }
            } else if (colors[neighbor] == color) {
                return false;
            }
        }
        return true;
    }

    static boolean isBipartite(int n, List<Integer>[] graph) {
        int[] colors = new int[n + 1];
        Arrays.fill(colors, -1);

        for (int i = 1; i <= n; i++) {
            if (colors[i] == -1) {
                if (!dfs(graph, colors, i, 0)) {
                    return false;
                }
            }
        }
        return true;
    }
}

 

BFS

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine().trim());

        for (int t = 0; t < k; t++) {
            String[] condition = br.readLine().split(" ");
            int vertex = Integer.parseInt(condition[0]);
            int edge = Integer.parseInt(condition[1]);

            List<Integer>[] adjList = new ArrayList[vertex + 1];
            for (int i = 0; i <= vertex; i++) {
                adjList[i] = new ArrayList<>();
            }

            for (int i = 0; i < edge; i++) {
                String[] edgeInfo = br.readLine().split(" ");
                int u = Integer.parseInt(edgeInfo[0]);
                int v = Integer.parseInt(edgeInfo[1]);

                adjList[u].add(v);
                adjList[v].add(u);
            }

            System.out.println(isBipartite(vertex, adjList) ? "YES" : "NO");
        }
    }

    static boolean bfs(List<Integer>[] graph, boolean[] visited, int[] colors, int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;
        colors[start] = 1;

        while (!queue.isEmpty()) {
            int node = queue.poll();

            for (int neighbor : graph[node]) {
                if (!visited[neighbor]) {
                    queue.add(neighbor);
                    visited[neighbor] = true;
                    colors[neighbor] = -colors[node];
                } else if (colors[neighbor] == colors[node]) {
                    return false;
                }
            }
        }
        return true;
    }

    static boolean isBipartite(int n, List<Integer>[] graph) {
        boolean[] visited = new boolean[n + 1];
        int[] colors = new int[n + 1];
        Arrays.fill(colors, 0);

        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                if (!bfs(graph, visited, colors, i)) {
                    return false;
                }
            }
        }
        return true;
    }
}