[Algorithm] 그래프와 순회 유형 모음

경로 찾기 문제

• 특정 노드에서 다른 노드로의 경로가 존재하는지 확인
• 예: 미로 탈출, 두 지점 사이의 연결 여부

기본적인 DFS를 통해 특정 정점에서 도달 가능한 정점을 찾는다거나, 도달 가능한 정점의 수를 세는 것이 가능하다.

단순히 그 점에서 DFS를 한 번 수행하면 된다.

예제 문제 - 바이러스

백준 2606번: 바이러스(S3)

public class Main {

    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    static int ret = 0;

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

        graph = new ArrayList[V + 1];
        visited = new boolean[V + 1];
        for (int i = 1; i <= V; i++) {
            graph[i] = new ArrayList<>();
        }

        StringTokenizer st;
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a].add(b);
            graph[b].add(a);
        }

        dfs(1);

        System.out.println(ret);
    }

    static void dfs(int node) {
        visited[node] = true;

        for (int next : graph[node]) {
            if (!visited[next]) {
                bfs(next);
                ++ret;
            }
        }
    }
}

연결 요소 (Connected Components) 찾기

• 그래프에서 연결된 모든 부분을 찾아 개수 세기
• 예: 섬의 개수 찾기 (2D 격자)

DFS 혹은 BFS로 모두 해결 가능하다. 공간 복잡도를 줄이기 위해 DFS를 사용하는 것이 일반적이다.
특정 요소에서 DFS를 한 번 수행하여 방문할 수 있는 모든 점들은 하나로 연결된 요소라고 볼 수 있다.
이를 (방문하지 않은) 모든 요소에 대해 수행하여, 연결된 요소의 개수를 구할 수 있다.

예제 문제 - 유기농 배추

백준 1012번: 유기농 배추(S2)

public class Main {

    static boolean[][] board;
    static boolean[][] visited;
    static int[] dy = new int[]{-1, 0, 1, 0};
    static int[] dx = new int[]{0, -1, 0, 1};
    static int M, N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());

            board = new boolean[M][N];
            visited = new boolean[M][N];

            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                board[a][b] = true;
            }

            // 연결 요소의 개수
            int ret = 0;
            for (int i = 0; i < M; i++) {
                for (int j = 0; j < N; j++) {
                    if (board[i][j] && !visited[i][j]) {
                        ++ret;
                        dfs(i, j);
                    }
                }
            }

            sb.append(ret).append("\n");
        }

        System.out.println(sb);
    }

    static void dfs(int y, int x) {
        visited[y][x] = true;
        for (int dir = 0; dir < 4; dir++) {
            int ny = y + dy[dir];
            int nx = x + dx[dir];

            if (ny < 0 || nx < 0 || ny >= M || nx >= N) continue;
            if (visited[ny][nx] || !board[ny][nx]) continue;

            dfs(ny, nx);
        }
    }
}

가중치가 없는 그래프에서 최단 거리 구하기

• 가중치가 없는 그래프에서 최단 경로 찾기
• 예: 미로의 최소 이동 칸 수, 특정 거리 이하의 정점 탐색

DFS로도 가능하지만, 보통 최단 거리를 보장하기 위해 BFS로 해결한다.

거리를 담는 dist 배열을 선언하는 것이 특징이며, 이를 모두 -1로 초기화한 후, dist의 요소가 -1이 아닌 경우에만, 즉 이전에 방문하지 않은 경우에만 값을 업데이트 하여 최단 거리를 구하는 방식이다.

(dist[i] != -1 이라는 것은 정점 i를 방문한적이 없다는 의미이다. visited[i] = false와 같다고 볼 수 있다.)

예제 문제 - 미로 탐색

백준 2178번: 미로 탐색(S1)

public class Main {

    static int[] dy = new int[]{-1, 0, 1, 0};
    static int[] dx = new int[]{0, -1, 0, 1};
    static char[][] graph;
    static int[][] dist;
    static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        graph = new char[N][M];
        dist = new int[N][M];
        for (int i = 0; i < N; i++) {
            graph[i] = br.readLine().toCharArray();
        }

        Queue<int[]> queue = new LinkedList<>();

        queue.add(new int[]{0, 0});
        dist[0][0] = 1;

        while(!queue.isEmpty()) {
            int[] curr = queue.poll();
            int y = curr[0];
            int x = curr[1];
            for (int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];

                if (nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
                if(dist[ny][nx] != 0 || graph[ny][nx] == '0') continue;

                queue.add(new int[]{ny, nx});
                dist[ny][nx] = 1 + dist[y][x];
            }
        }

        System.out.println(dist[N - 1][M - 1]);
    }
}

• 여기서는 dist 배열을 -1이 아닌 0으로 그냥 두었다. 0이라는 값이 가능한 경우에는 -1로 초기화하고, 그렇지 않은 경우에는 0으로 두자.

사이클 탐지

사이클 탐지는 여러가지 방법으로 가능하며, 무향 그래프인지 유향 그래프인지에 따라 다르다.

1. 무방향 그래프에서 사이클 탐지
   • DFS (깊이 우선 탐색) 이용
   • Union-Find (서로소 집합) 알고리즘 이용 가능
2. 방향 그래프에서 사이클 탐지
   • DFS와 위상 정렬로 탐지 가능
   • DFS에서는 백 에지 (Back Edge)를 통해 사이클 확인
   • 위상 정렬이 실패하면 사이클 존재

무방향 그래프에서의 사이클 탐지 - DFS

DFS로 탐색 중 부모 노드가 아닌데 이미 방문한 노드가 있으면 사이클

-> (visited[next] && next != parent)

import java.util.*;

public class UndirectedCycleDetection {
    static List<Integer>[] graph;
    static boolean[] visited;

    public static void main(String[] args) {
        int n = 5;
        graph = new ArrayList[n + 1];
        visited = new boolean[n + 1];

        for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();

        // 간선 추가 (무방향 그래프)
        graph[1].add(2);
        graph[2].add(1);
        graph[1].add(3);
        graph[3].add(1);
        graph[2].add(4);
        graph[4].add(2);
        graph[3].add(5);
        graph[5].add(3);
        graph[4].add(5);
        graph[5].add(4);  // 사이클

        boolean hasCycle = false;
        for (int i = 1; i <= n; i++) {
            if (!visited[i] && isCycle(i, -1)) {  // 시작점의 부모는 -1
                hasCycle = true;
                break;
            }
        }

        System.out.println(hasCycle ? "Cycle detected!" : "No cycle.");
    }

    static boolean isCycle(int node, int parent) {
        visited[node] = true;

        for (int next : graph[node]) {
            if (!visited[next]) {
                if (isCycle(next, node)) return true;
            } else if (next != parent) {  // 부모가 아닌데 방문된 노드
                return true;  // 사이클 존재
            }
        }

        return false;
    }
}

무방향 그래프에서의 사이클 탐지 - Union Find

노드가 같은 집합에 속해있는데 또 연결하려 하면 사이클

public class UnionFindCycleDetection {
    static int[] parent;

    public static void main(String[] args) {
        int n = 5;
        parent = new int[n + 1];

        // 초기화
        for (int i = 1; i <= n; i++) parent[i] = i;

        // 간선 정보
        int[][] edges = {{1, 2}, {1, 3}, {2, 4}, {3, 5}, {4, 5}};  // 사이클 존재

        boolean hasCycle = false;
        for (int[] edge : edges) {
            if (!union(edge[0], edge[1])) {  // 사이클 발견 시
                hasCycle = true;
                break;
            }
        }

        System.out.println(hasCycle ? "Cycle detected!" : "No cycle.");
    }

    static int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    static boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return false;  // 사이클 발견

        parent[rootX] = rootY;
        return true;
    }
}

방향 그래프에서의 사이클 탐지 - DFS 사용

• DFS 중 방문 중인 노드로 돌아가면 사이클 = DFS 중 아직 탐색이 종료되지 않은 노드로 돌아가면 사이클
• finished 배열 추가

public class DirectedCycleDetection {
    static List<Integer>[] graph;
    static boolean[] visited;
    static boolean[] finished;

    public static void main(String[] args) {
        int n = 4;
        graph = new ArrayList[n + 1];
        visited = new boolean[n + 1];
        finished = new boolean[n + 1];

        for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();

        // 간선 추가 (방향 그래프)
        graph[1].add(2);
        graph[2].add(3);
        graph[3].add(4);
        graph[4].add(2);  // 사이클

        boolean hasCycle = false;
        for (int i = 1; i <= n; i++) {
            if (!visited[i] && isCycle(i)) {
                hasCycle = true;
                break;
            }
        }

        System.out.println(hasCycle ? "Cycle detected!" : "No cycle.");
    }

    static boolean isCycle(int node) {
        visited[node] = true;

        for (int next : graph[node]) {
            if (!visited[next]) {         // 아직 방문하지 않은 경우
                if (isCycle(next)) return true;  // 사이클 발견
            } else if (!finished[next]) { // 방문했지만 완료되지 않은 경우 (탐색 중)
                return true;  // 사이클 존재
            }
        }

        finished[node] = true;  // 탐색 완료 표시
        return false;
    }
}

이분 그래프 판별

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph)라 부른다.

 

이분 그래프인지 판별하기 위해서는 정점을 탐색하는 과정 중 각 정점을 이전 정점(부모)와 다른 색으로 칠하는 과정을 반복하면서, 만약 인접한 두 정점이 동일한 색으로 칠해진다면 이분 그래프가 아니라고 볼 수 있다.

예제 문제 - 이분 그래프

백준 1707번: 이분 그래프(G4)

public class Main {

    static final int RED = 1, BLACK = -1, UNCOLORED = 0;
    static ArrayList<Integer>[] graph;
    static int[] color; // 1 -> RED, 0 -> 무색(아직 집합에 속하지 않음), -1 -> BLACK

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

        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        while (K-- > 0) {
            st = new StringTokenizer(br.readLine());
            int V = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());

            graph = new ArrayList[V + 1];
            color = new int[V + 1];

            for (int i = 1; i <= V; i++) {
                graph[i] = new ArrayList<>();
            }

            for (int i = 0; i < E; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                graph[a].add(b);
                graph[b].add(a);
            }

            boolean isBipartite = true;
            for (int i = 1; i <= V; i++) {
                if (color[i] == 0 && !checkIsBipartite(i, RED)) {
                    isBipartite = false;
                    break;
                }
            }

            sb.append(isBipartite ? "YES" : "NO").append("\n");
        }

        System.out.println(sb);
    }

    static boolean checkIsBipartite(int node, int c) {
        color[node] = c;

        for (int next : graph[node]) {
            if (color[next] == UNCOLORED) {  // 인접 노드가 아직 색칠되지 않은 경우
                if (!checkIsBipartite(next, -c)) {  // 반대 색으로 색칠 시도
                    return false;
                }
            } else if (color[next] == c) {  // 인접 노드가 같은 색인 경우
                return false;
            }
        }
        return true;
    }
}

• 인접 노드가 아직 색칠되지 않은 경우, 현재 노드와 반대 색으로 색칠을 시도한다.
• 인접 노드가 색칠되어 있고, 현재 노드와 같은 색인 경우 이분 그래프가 아니다.