algorithm practice

- 단계별 문제풀기

37. 강한 연결 요소

Strongly connected component를 다뤄 봅시다.

8. TV Show Game

16367번

2-SAT이 아닌 것처럼 보이지만 2-SAT으로 바꿀 수 있는 문제

이번 문제는 영어로 되어 있어 해석을 가져왔다. 각 램프는 빨간색 또는 파란색의 색을 가지고 있다. 그러나 램프를 켜야 램프의 색상을 식별할 수 있다. 게임 참가자들은 무작위로 세 개의 램프를 선택하고 램프의 색을 추측하도록 요청 받는다. 그런 다음 각 참가자는 선택된 램프의 예측된 색상이 기록된 종이를 게임 진행자인 다우다 씨에게 제출한다. 모든 램프가 켜지면 각 참가자는 예측된 색상의 수가 램프의 실제 색상과 얼마나 일치하는지 확인하고, 두 가지 이상의 색상이 일치하면 상품으로 멋진 선물을 받게 된다.
즉, 게임 참가자들로부터 받은 모든 논문을 검토한 후 가능한 모든 참가자가 상품을 받을 수 있도록 각 램프의 색상을 조정하려고 할 때, 예측된 색상에 대한 정보를 바탕으로, 모든 참가자들에게 경품을 받을 수 있도록 모든 램프의 색상을 조정할 수 있는지 여부를 결정하는 프로그램을 작성하는 문제이다.

SCC를 찾는 알고리즘은 크게 이 두가지 방법이다.

• 타잔 알고리즘 모든 정점에 대해 DFS를 수행하여 SCC를 찾는 알고리즘으로, 코사라주 알고리즘에 비해 적용이 더 쉽다고 한다. ① 인접 정점에 방문하며 자기 자신을 스택에 넣고, 재귀적으로 DFS를 수행한다. ② 인접 정점에 방문했지만, 아직 처리중인 상태일 경우, 작은 값으로 부모값을 갱신한다. ③ 부모 노드의 DFS가 끝난 경우에는, 자신의 id값이 스택에서 나올 때까지 스택에 있는 노드들을 pop하고 scc 배열에 추가한다. ④ 만들어진 하나의 scc를 전체 SCC 배열에 추가한다. (구현이 더 어렵지만, 활용도는 더 높다고 한다.)
  
• 코사라주 알고리즘 주어진 방향 그래프의 역방향 그래프와 스택을 사용하여 SCC를 구하는 알고리즘이다. 방향, 역방향 그래프가 동일한 SCC를 구성한다는 것을 이용한 방법이다. ① 주어지는 방향 그래프와 그 그래프의 역방향 그래프를 만든다. ② 정점을 담을 스택을 만들고 임의의 정점부터 DFS를 수행한다. ③ DFS가 끝나는 순서대로 스택에 삽입하고, 아직 방문하지 않은 정점에 대해 DFS를 수행한다. ④ 모든 정점이 스택에 담긴 후에는 스택을 pop하여 나오는 정점부터 역방향 그래프에서 DFS를 수행한다.. 이미 방문한 정점은 pop만 시행한다. ⑤ 이때 탐색되는 모든 정점을 SCC로 묶는다. 이것을 스택이 빌 때까지 진행한다. (타잔 알고리즘에 비해 구현이 더 쉬운 편이라고 한다.)

저번 문제들과 유사하고, scc 응용 문제이다. 타잔 알고리즘을 이용했다..!

Java / Python

• Java

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

public class Main {
    static int N, V, num;
    static ArrayList<ArrayList<Integer>> graph, scc_arr;
    static int[] parent, CNF;
    static boolean[] visit; // SCC 확정된 정점 확인
    static char[] color;
    static Stack<Integer> stack;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        parent = new int[2 * N + 1];
        visit = new boolean[2 * N + 1];
        stack = new Stack<>();
        num = V = 0;
        color = new char[N + 1];
        CNF = new int[2 * N + 1];
        graph = new ArrayList<>();
        scc_arr = new ArrayList<>();

        for (int i = 0; i < 2 * N + 1; i++) {
            graph.add(new ArrayList<>());
        }

        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int[] E = new int[3];
            for (int i = 0; i < 3; i++) {
                int x = Integer.parseInt(st.nextToken());
                char c = st.nextToken().charAt(0);
                if (c == 'R')
                    E[i] = x;
                else
                    E[i] = -x;
            }

            graph.get(validate(-E[0])).add(validate(E[1]));
            graph.get(validate(-E[1])).add(validate(E[0]));
            graph.get(validate(-E[0])).add(validate(E[2]));
            graph.get(validate(-E[2])).add(validate(E[0]));
            graph.get(validate(-E[1])).add(validate(E[2]));
            graph.get(validate(-E[2])).add(validate(E[1]));
        }

        for (int i = 1; i < 2 * N + 1; i++) {
            if (!visit[i]) {
                SCC(i);
            }
        }

        if (isTrue()) {
            bw.write(topologySort() + "\n");
        } else {
            bw.write("-1\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static int validate(int n) {
        return (0 < n && n < N + 1) ? n : -n + N;
    }

    private static String topologySort() {
        for (int i = V - 1; i > -1; i--) {
            for (int j : scc_arr.get(i)) {
                int cur = Math.abs(validate(j));
                if (color[cur] == '\0') {
                    if (j > N)
                        color[cur] = 'R';
                    else
                        color[cur] = 'B';
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < N + 1; i++) {
            sb.append(color[i]);
        }

        return sb.toString();
    }

    private static boolean isTrue() {
        for (int i = 1; i < N + 1; i++) {
            if (CNF[i] == CNF[i + N])
                return false;
        }
        return true;
    }

    private static int SCC(int idx) {
        parent[idx] = ++num;
        stack.push(idx);
        int root = parent[idx];

        for (int next : graph.get(idx)) {
            if (parent[next] == 0)
                root = Math.min(root, SCC(next));
            else if (!visit[next])
                root = Math.min(root, parent[next]);
        }

        if (root == parent[idx]) {
            ArrayList<Integer> tmp = new ArrayList<>();
            while (!stack.isEmpty()) {
                int top = stack.pop();
                tmp.add(top);
                visit[top] = true;
                CNF[top] = V;

                if (top == idx)
                    break;
            }
            V++;
            scc_arr.add(tmp);
        }
        return root;
    }
}

• Python

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

def SCC(node):
    global idx, scc_num
    visit[node] = idx
    root = idx
    idx += 1
    stack.append(node)

    for nxt in graph[node]:
        if not visit[nxt]:
            root = min(root, SCC(nxt))
        elif not check[nxt]:
            root = min(root, visit[nxt])

    if root == visit[node]:
        while stack:
            top = stack.pop()
            check[top] = 1
            scc_arr[top] = scc_num
            if node == top:
                break

        scc_num += 1

    return root

def neg(a):
    if a <= N: return a + N
    else: return a - N

# main part
N, M = map(int, input().rstrip().split())
graph = [[] for _ in range(2 * N + 1)]
for _ in range(M):
    # R -> true, B -> false
    a, RB1, b, RB2, c, RB3 = list(input().rstrip().split())
    a, b, c = map(int, [a, b, c])
    if RB1 == 'B': a = a + N
    if RB2 == 'B': b = b + N
    if RB3 == 'B': c = c + N
    graph[neg(a)].append(b)
    graph[neg(b)].append(a)
    graph[neg(b)].append(c)
    graph[neg(c)].append(b)
    graph[neg(c)].append(a)
    graph[neg(a)].append(c)

# 타잔 알고리즘
idx = scc_num = 0
check = [False for _ in range(2 * N + 1)]
scc_arr = [0 for _ in range(2 * N + 1)]
visit = [0 for _ in range(2 * N + 1)]
stack = []
for i in range(1, 2 * N + 1):
    if check[i]: continue
    SCC(i)

for i in range(1, N + 1):
    if scc_arr[i] == scc_arr[i + N]:
        print(-1)
        exit(0)

for i in range(1, N + 1):
    if scc_arr[i] > scc_arr[i + N]:
        print('B', end='')
    else:
        print('R', end='')

헤딩(Heading)

(#) 개수에 따라서 제목의 수준을 구별한다. 문서 구조의 기본이다.

# h1
## h2
### h3
// 위와 같이 이용

리스트

목록을 표시하기 위해 사용

( *. -) : 리스트(List) / 순서 없는 리스트

(1.) : 순서가 있는 리스트

1. 이렇게 순서가 생김

코드 블럭(Code Block)

특정 언어를 명시하면 Syntax Highlighting을 지원한다.

print("Hello World!")

• 인라인 코드 블럭

print("Hi")

링크 (link)

다른 페이지로 이동하는 링크를 삽입한다.

파일 경로를 넣어 다운로드 가능한 링크로 만들 수 있다.

[보여지는 문장](링크 경로)

google

이미지

이미지 삽입

너비와 높이 조절 불가 (HTML 태그 사용하면 가능)

![이미지 텍스트](image_url)

텍스트 강조

굵게, 기울임, 취소선

**Bold** *italic* ~~취소선~~ // * 대신 _로 대체 가능

Bold italic 취소선

수평선

단락 구분을 위해 사용

---  
// -, *, _ 로 대체 가능

인용문

인용을 위한 단락 생성

> 인용문

인용문

하위 인용문

Table

표 생성하기

| header01 | header02 | 
// 이런식으로 작성하면 typora에서는 자동으로 표 모양 생성 

algorithm practice

- 단계별 문제풀기

37. 강한 연결 요소

Strongly connected component를 다뤄 봅시다.

7. 아이돌

3648번

상근이가 진출하면서 동시에 2-SAT을 성립시킬 수 있는지 판별하는 문제

아이돌 예선에 참가하는 상근이가 심사위원의 의심을 받지 않으면서, 다음 라운드에 진출하는 목록을 만들 수 있는지를 알고 싶어 한다. 당연히 이 목록에는 상근이가 포함되어 있어야 한다. 각 심사위원이 투표한 결과가 주어졌을 때, 상근이가 포함된 다음 라운드 진출 목록을 만들 수 있는지 없는지를 구하는 프로그램을 작성하는 문제이다. 심사위원이 내야하는 두 개의 표 중 하나는 결과에 영향을 미쳐야하므로, 하나의 OR 절로 묶어낼 수 있고, 모든 심사위원의 투표 결과로 진출 목록을 만들어내야 하기 때문에 2-SAT 문제로 볼 수 있다. 진출 목록을 만들 수 있는지 없는지 확인하고 상근이도 진출 목록에 포함시킨다.

SCC를 찾는 알고리즘은 크게 이 두가지 방법이다.

• 타잔 알고리즘 모든 정점에 대해 DFS를 수행하여 SCC를 찾는 알고리즘으로, 코사라주 알고리즘에 비해 적용이 더 쉽다고 한다. ① 인접 정점에 방문하며 자기 자신을 스택에 넣고, 재귀적으로 DFS를 수행한다. ② 인접 정점에 방문했지만, 아직 처리중인 상태일 경우, 작은 값으로 부모값을 갱신한다. ③ 부모 노드의 DFS가 끝난 경우에는, 자신의 id값이 스택에서 나올 때까지 스택에 있는 노드들을 pop하고 scc 배열에 추가한다. ④ 만들어진 하나의 scc를 전체 SCC 배열에 추가한다. (구현이 더 어렵지만, 활용도는 더 높다고 한다.)
  

• 코사라주 알고리즘 주어진 방향 그래프의 역방향 그래프와 스택을 사용하여 SCC를 구하는 알고리즘이다. 방향, 역방향 그래프가 동일한 SCC를 구성한다는 것을 이용한 방법이다. ① 주어지는 방향 그래프와 그 그래프의 역방향 그래프를 만든다. ② 정점을 담을 스택을 만들고 임의의 정점부터 DFS를 수행한다. ③ DFS가 끝나는 순서대로 스택에 삽입하고, 아직 방문하지 않은 정점에 대해 DFS를 수행한다. ④ 모든 정점이 스택에 담긴 후에는 스택을 pop하여 나오는 정점부터 역방향 그래프에서 DFS를 수행한다.. 이미 방문한 정점은 pop만 시행한다. ⑤ 이때 탐색되는 모든 정점을 SCC로 묶는다. 이것을 스택이 빌 때까지 진행한다. (타잔 알고리즘에 비해 구현이 더 쉬운 편이라고 한다.)

저번 문제들과 유사하고, scc 응용 문제이다. 타잔 알고리즘을 이용했다..!

Java / Python

• Java

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

public class Main {
    static int N, V, num;
    static ArrayList<Integer>[] graph;
    static int[] parent, CNF;
    static boolean[] visit; // SCC 확정된 정점 확인
    static Stack<Integer> stack;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        while (true) {
            String input = br.readLine();
            if (input == null)
                break;
            st = new StringTokenizer(input, " ");

            N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            parent = new int[2 * N + 1];
            visit = new boolean[2 * N + 1];
            stack = new Stack<>();
            num = 0;
            V = 0;
            CNF = new int[2 * N + 1];
            graph = new ArrayList[2 * N + 1];

            for (int i = 0; i < 2 * N + 1; i++) {
                graph[i] = new ArrayList<>();
            }
            graph[validate(-1)].add(1);

            while (M-- > 0) {
                st = new StringTokenizer(br.readLine(), " ");

                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());

                graph[validate(-u)].add(validate(v));
                graph[validate(-v)].add(validate(u));
            }

            for (int i = 1; i < 2 * N + 1; i++) {
                if (!visit[i]) {
                    SCC(i);
                }
            }

            bw.write(printR());
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static int validate(int n) {
        return (0 < n && n < N + 1) ? n : -n + N;
    }

    private static String printR() {
        for (int i = 1; i < N + 1; i++) {
            if (CNF[i] == CNF[i + N]) return "no\n";
        }
        return "yes\n";
    }

    private static int SCC(int idx) {
        parent[idx] = ++num;
        stack.push(idx);
        int root = parent[idx];

        for (int next : graph[idx]) {
            if (parent[next] == 0)
                root = Math.min(root, SCC(next));
            else if (!visit[next])
                root = Math.min(root, parent[next]);
        }

        if (root == parent[idx]) {
            while (!stack.isEmpty()) {
                int top = stack.pop();
                CNF[top] = V;
                visit[top] = true;
                if (top == idx)
                    break;
            }
            V++;
        }
        return root;
    }
}

• Python

import sys
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline

def SCC(node):
    global idx, scc_num
    visit[node] = idx
    idx += 1
    stack.append(node)
    root = visit[node]
    for nxt in graph[node]:
        if not visit[nxt]:
            root = min(root, SCC(nxt))
        elif not check[nxt]:
            root = min(root, visit[nxt])
    if root == visit[node]:
        cur_scc = []
        while True:
            top = stack.pop()
            check[top] = True
            cur_scc.append(top)
            CNF[top] = scc_num
            if top == node:
                break
        scc_num+=1
        scc_arr.append(cur_scc)
    return root

while True:
    inputline  = input()
    if inputline == "":
        break
    N, M = map(int, inputline.split())
    graph = [[] for _ in range(2*N)]
    for _ in range(M):
        a, b = map(int, input().split())
        if a < 0 :  a = N - a
        if b < 0 : b = N -b
        a -= 1
        b -= 1
        graph[(a+N)%(2*N)].append(b)
        graph[(b+N)%(2*N)].append(a)
    graph[N].append(0)

    visit = [False] * (2*N)
    check = [False] * (2*N)
    idx = 1
    scc_num = 0
    CNF = [-1]*(2*N)
    stack = []
    scc_arr = []

    for i in range(2*N):
        if not visit[i]:
            SCC(i)
    for i in range(N):
        if CNF[i] == CNF[N+i]:
            print("no")
            break
    else:
        print("yes")

algorithm practice

- 단계별 문제풀기

37. 강한 연결 요소

Strongly connected component를 다뤄 봅시다.

6. 2-SAT - 4

11281번

2-SAT의 해를 출력해 봅시다.

2-SAT은 N개의 불리언 변수 (x_1, x_2, ..., x_n)가 있을 때, 2-CNF 식을 true로 만들기위해 (x_i)를 어떤 값으로 정해야하는지를 구하는 문제이다. 이번 문제는 변수의 개수 N과 절의 개수 M, 그리고 식 (f)가 주어졌을 때, 식 (f)를 true로 만들 수 있는지 없는지를 구하는 프로그램을 작성하는 문제이다.

SCC를 찾는 알고리즘은 크게 이 두가지 방법이다.

• 타잔 알고리즘 모든 정점에 대해 DFS를 수행하여 SCC를 찾는 알고리즘으로, 코사라주 알고리즘에 비해 적용이 더 쉽다고 한다. ① 인접 정점에 방문하며 자기 자신을 스택에 넣고, 재귀적으로 DFS를 수행한다. ② 인접 정점에 방문했지만, 아직 처리중인 상태일 경우, 작은 값으로 부모값을 갱신한다. ③ 부모 노드의 DFS가 끝난 경우에는, 자신의 id값이 스택에서 나올 때까지 스택에 있는 노드들을 pop하고 scc 배열에 추가한다. ④ 만들어진 하나의 scc를 전체 SCC 배열에 추가한다. (구현이 더 어렵지만, 활용도는 더 높다고 한다.)
  

• 코사라주 알고리즘 주어진 방향 그래프의 역방향 그래프와 스택을 사용하여 SCC를 구하는 알고리즘이다. 방향, 역방향 그래프가 동일한 SCC를 구성한다는 것을 이용한 방법이다. ① 주어지는 방향 그래프와 그 그래프의 역방향 그래프를 만든다. ② 정점을 담을 스택을 만들고 임의의 정점부터 DFS를 수행한다. ③ DFS가 끝나는 순서대로 스택에 삽입하고, 아직 방문하지 않은 정점에 대해 DFS를 수행한다. ④ 모든 정점이 스택에 담긴 후에는 스택을 pop하여 나오는 정점부터 역방향 그래프에서 DFS를 수행한다.. 이미 방문한 정점은 pop만 시행한다. ⑤ 이때 탐색되는 모든 정점을 SCC로 묶는다. 이것을 스택이 빌 때까지 진행한다. (타잔 알고리즘에 비해 구현이 더 쉬운 편이라고 한다.)

저번 문제들과 유사하고, scc 응용 문제이다. 타잔 알고리즘을 이용했다..!

Java / Python

• Java

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

public class Main {
    static int N, V, num;
    static ArrayList<ArrayList<Integer>> graph, scc_arr;
    static int[] parent, compare, CNF;
    static boolean[] visit; // SCC 확정된 정점 확인
    static Stack<Integer> stack;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        parent = new int[2 * N + 1];
        compare = new int[2 * N + 1];
        visit = new boolean[2 * N + 1];
        stack = new Stack<>();
        num = 0;
        V = 0;
        CNF = new int[2 * N + 1];
        Arrays.fill(CNF, -1);

        graph = new ArrayList<>();
        scc_arr = new ArrayList<>();
        for (int i = 0; i < 2 * N + 1; i++) {
            graph.add(new ArrayList<>());
        }

        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());

            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            graph.get(validate(-u)).add(validate(v));
            graph.get(validate(-v)).add(validate(u));
        }

        for (int i = 1; i < 2 * N + 1; i++) {
            if (!visit[i]) {
                SCC(i);
            }
        }
        int sts = 1;
        for (int i = 1; i < N + 1; i++) {
            if (compare[i] == compare[i + N])
                sts = 0;
        }

        bw.write(sts + "\n");
        if (sts == 1)
            bw.write(setCNF() + "\n");

        bw.flush();
        bw.close();
        br.close();
    }

    private static int validate(int n) {
        return (0 < n && n < N + 1) ? n : -n + N;
    }

    private static String setCNF() {
        for (int i = V - 1; i > -1; i--) {
            for (int j : scc_arr.get(i)) {
                int now = Math.abs(validate(j));
                if (CNF[now] == -1) {
                    if (j > N) {
                        CNF[now] = 1;
                    } else {
                        CNF[now] = 0;
                    }
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < N + 1; i++) {
            sb.append(CNF[i]).append(' ');
        }
        return sb.toString();
    }

    private static int SCC(int idx) {
        parent[idx] = ++num;
        stack.push(idx);

        int root = parent[idx];
        for (int next : graph.get(idx)) {
            if (parent[next] == 0)
                root = Math.min(root, SCC(next));
            else if (!visit[next])
                root = Math.min(root, parent[next]);
        }

        if (root == parent[idx]) {
            ArrayList<Integer> tmp = new ArrayList<>();
            while (!stack.isEmpty()) {
                int top = stack.pop();
                tmp.add(top);
                visit[top] = true;
                compare[top] = V;

                if (top == idx)
                    break;
            }
            V++;
            scc_arr.add(tmp);
        }
        return root;
    }
}

• Python

import sys
sys.setrecursionlimit(10 ** 5)

N, M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(2 * N + 1)]

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    graph[-a].append(b)
    graph[-b].append(a)

scc_num = 1
idx = 1
stack = []
scc_idx = [0] * (2 * N + 1)
check = [0] * (2 * N + 1)
visit = [0] * (2 * N + 1)

def SCC(node):
    global idx, scc_num
    visit[node] = idx
    root = idx
    idx += 1
    stack.append(node)

    for nxt in graph[node]:
        if not visit[nxt]:
            root = min(root, SCC(nxt))
        elif not check[nxt]:
            root = min(root, visit[nxt])

    if root == visit[node]:
        while stack:
            top = stack.pop()
            check[top] = 1
            scc_idx[top] = scc_num
            if node == top:
                break

        scc_num += 1

    return root

for i in range(1, 2 * N + 1):
    if not visit[i]:
        SCC(i)

result = [0] * N
for i in range(1, N + 1):
    if scc_idx[i] == scc_idx[-i]:
        print(0)
        break
    if scc_idx[i] < scc_idx[-i]:
        result[i - 1] = 1
else:
    print(1)
    print(*result)

algorithm practice

- 단계별 문제풀기

37. 강한 연결 요소

Strongly connected component를 다뤄 봅시다.

5. 2-SAT - 3

11280번

SCC를 응용하여 풀 수 있는 2-SAT 문제에 대해 배워 봅시다.

2-SAT은 N개의 불리언 변수 (x_1, x_2, ..., x_n)가 있을 때, 2-CNF 식을 true로 만들기위해 (x_i)를 어떤 값으로 정해야하는지를 구하는 문제이다. 이번 문제는 변수의 개수 N과 절의 개수 M, 그리고 식 (f)가 주어졌을 때, 식 (f)를 true로 만들 수 있는지 없는지를 구하는 프로그램을 작성하는 문제이다. 식 (f)를 true로 만들 수 있으면 1을, 없으면 0을 출력한다.

SCC를 찾는 알고리즘은 크게 이 두가지 방법이다.

• 타잔 알고리즘 모든 정점에 대해 DFS를 수행하여 SCC를 찾는 알고리즘으로, 코사라주 알고리즘에 비해 적용이 더 쉽다고 한다. ① 인접 정점에 방문하며 자기 자신을 스택에 넣고, 재귀적으로 DFS를 수행한다. ② 인접 정점에 방문했지만, 아직 처리중인 상태일 경우, 작은 값으로 부모값을 갱신한다. ③ 부모 노드의 DFS가 끝난 경우에는, 자신의 id값이 스택에서 나올 때까지 스택에 있는 노드들을 pop하고 scc 배열에 추가한다. ④ 만들어진 하나의 scc를 전체 SCC 배열에 추가한다. (구현이 더 어렵지만, 활용도는 더 높다고 한다.)
  

• 코사라주 알고리즘 주어진 방향 그래프의 역방향 그래프와 스택을 사용하여 SCC를 구하는 알고리즘이다. 방향, 역방향 그래프가 동일한 SCC를 구성한다는 것을 이용한 방법이다. ① 주어지는 방향 그래프와 그 그래프의 역방향 그래프를 만든다. ② 정점을 담을 스택을 만들고 임의의 정점부터 DFS를 수행한다. ③ DFS가 끝나는 순서대로 스택에 삽입하고, 아직 방문하지 않은 정점에 대해 DFS를 수행한다. ④ 모든 정점이 스택에 담긴 후에는 스택을 pop하여 나오는 정점부터 역방향 그래프에서 DFS를 수행한다.. 이미 방문한 정점은 pop만 시행한다. ⑤ 이때 탐색되는 모든 정점을 SCC로 묶는다. 이것을 스택이 빌 때까지 진행한다. (타잔 알고리즘에 비해 구현이 더 쉬운 편이라고 한다.)

저번 문제들과 유사하고, scc 응용 문제이다. 타잔 알고리즘을 이용했다..!

Java / Python

• Java

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

public class Main {
    static int N, num;
    static ArrayList<Integer>[] graph;
    static int[] order;
    static boolean[] visit; // SCC 확정된 정점 확인
    static Stack<Integer> stack;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        graph = new ArrayList[2 * N + 1];
        order = new int[2 * N + 1];
        visit = new boolean[2 * N + 1];
        stack = new Stack<>();

        for (int i = 0; i < 2 * N + 1; i++) {
            graph[i] = new ArrayList<>();
        }

        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());

            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            graph[validate(-u)].add(validate(v));
            graph[validate(-v)].add(validate(u));
        }

        boolean flag = true;
        for (int i = 1; i < 2 * N + 1; i++) {
            if (!visit[i]) {
                if (SCC(i) == -1) {
                    flag = false;
                    break;
                }
            }
        }

        if (flag)
            bw.write("1\n");
        else
            bw.write("0\n");

        bw.flush();
        bw.close();
        br.close();
    }

    private static int validate(int n) {
        if (0 < n && n < N + 1)
            return n;
        return -n + N;
    }

    private static int SCC(int idx) {
        order[idx] = ++num;
        stack.add(idx);
        int root = order[idx];

        for (int next : graph[idx]) {
            if (order[next] == 0)
                root = Math.min(root, SCC(next));
            else if (!visit[next])
                root = Math.min(root, order[next]);
        }

        if (root == order[idx]) {
            boolean[] check = new boolean[N + 1];
            while (!stack.isEmpty()) {
                int top = stack.pop();
                int temp = validate(top);

                if (temp < 0)
                    temp *= -1;
                if (check[temp])
                    return -1;

                check[temp] = true;
                visit[top] = true;

                if (top == idx)
                    break;
            }
        }
        return root;
    }
}

• Python

import sys
sys.setrecursionlimit(10 ** 5)

N, M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(2 * N + 1)]

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    graph[-a].append(b)
    graph[-b].append(a)

scc_num = 1
idx = 1
stack = []
scc_idx = [0] * (2 * N + 1)
check = [0] * (2 * N + 1)
visit = [0] * (2 * N + 1)

def SCC(node):
    global idx, scc_num
    visit[node] = idx
    root = idx
    idx += 1
    stack.append(node)

    for nxt in graph[node]:
        if not visit[nxt]:
            root = min(root, SCC(nxt))
        elif not check[nxt]:
            root = min(root, visit[nxt])

    if root == visit[node]:
        while stack:
            top = stack.pop()
            check[top] = 1
            scc_idx[top] = scc_num
            if node == top:
                break

        scc_num += 1

    return root


for i in range(1, N + 1):
    if not visit[i]:
        SCC(i)

for i in range(1, N + 1):
    if scc_idx[i] == scc_idx[-i]:
        print(0)
        break
else:
    print(1)

algorithm practice

- 단계별 문제풀기

37. 강한 연결 요소

Strongly connected component를 다뤄 봅시다.

4. ATM

4013번

각각의 SCC를 하나로 묶은 다음 각 묶음마다 답을 계산하는 문제

이번 문제는 출발 장소에서 어떤 레스토랑까지 이동하면서 인출할 수 있는 현금의 최대 액수가 얼마인지를 계산하는 프로그램을 작성하는 문제이다.
( 예를 들어, 아래 그림처럼 도시에 6개의 교차로가 있다고 하자. 교차로는 원으로 표시되어 있고, 화살표는 도로를 나타낸다. 이중 원으로 표시된 교차로에는 레스토랑이 있다. 각 ATM 기기가 갖고 있는 현금의 액수는 교차로 위에 표시된 숫자이다. 이 예에서 현금 인출을 1번 교차로부터 시작한다면, 반디치는 1-2-4-1-2-3-5의 경로를 통해서 총 47의 현금을 인출할 수 있다. )

SCC를 찾는 알고리즘은 크게 이 두가지 방법이다.

• 타잔 알고리즘 모든 정점에 대해 DFS를 수행하여 SCC를 찾는 알고리즘으로, 코사라주 알고리즘에 비해 적용이 더 쉽다고 한다. ① 인접 정점에 방문하며 자기 자신을 스택에 넣고, 재귀적으로 DFS를 수행한다. ② 인접 정점에 방문했지만, 아직 처리중인 상태일 경우, 작은 값으로 부모값을 갱신한다. ③ 부모 노드의 DFS가 끝난 경우에는, 자신의 id값이 스택에서 나올 때까지 스택에 있는 노드들을 pop하고 scc 배열에 추가한다. ④ 만들어진 하나의 scc를 전체 SCC 배열에 추가한다. (구현이 더 어렵지만, 활용도는 더 높다고 한다.)
  

• 코사라주 알고리즘 주어진 방향 그래프의 역방향 그래프와 스택을 사용하여 SCC를 구하는 알고리즘이다. 방향, 역방향 그래프가 동일한 SCC를 구성한다는 것을 이용한 방법이다. ① 주어지는 방향 그래프와 그 그래프의 역방향 그래프를 만든다. ② 정점을 담을 스택을 만들고 임의의 정점부터 DFS를 수행한다. ③ DFS가 끝나는 순서대로 스택에 삽입하고, 아직 방문하지 않은 정점에 대해 DFS를 수행한다. ④ 모든 정점이 스택에 담긴 후에는 스택을 pop하여 나오는 정점부터 역방향 그래프에서 DFS를 수행한다.. 이미 방문한 정점은 pop만 시행한다. ⑤ 이때 탐색되는 모든 정점을 SCC로 묶는다. 이것을 스택이 빌 때까지 진행한다. (타잔 알고리즘에 비해 구현이 더 쉬운 편이라고 한다.)

저번 문제들과 유사하다. scc를 응용한 문제이며, scc를 구하고 bfs를 이용해서 풀 수 있었다. 조금 더 길고 복잡한 문제이다..

Java / Python

• Java

타잔 알고리즘 이용

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

public class Main {
    static int scc_total, num;
    static ArrayList<Integer>[] edges;
    static int[] order, scc_arr;
    static boolean[] visit; // SCC 확정된 정점 확인
    static Stack<Integer> stack;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); // 정점의 개수
        int M = Integer.parseInt(st.nextToken()); // 간선의 개수

        edges = new ArrayList[N + 1];

        for (int i = 0; i < N + 1; i++) {
            edges[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            edges[a].add(b);
        }

        scc_arr = new int[N + 1];
        order = new int[N + 1];
        visit = new boolean[N + 1];
        scc_total = num = 0;
        stack = new Stack<>();

        for (int i = 0; i < N; i++) {
            if (!visit[i])
                SCC(i);
        }

        int[] dp = new int[scc_total];
        int[] indegree = new int[scc_total];
        List<Integer>[] scc = new ArrayList[scc_total];
        for (int i = 0; i < scc_total; i++) {
            scc[i] = new ArrayList<>();
        }

        for (int i = 1; i < N + 1; i++) {
            st = new StringTokenizer(br.readLine());
            indegree[scc_arr[i]] += Integer.parseInt(st.nextToken());
            for (int j : edges[i]) {
                if (scc_arr[i] != scc_arr[j])
                    scc[scc_arr[i]].add(scc_arr[j]);
            }
        }

        st = new StringTokenizer(br.readLine());
        int s = scc_arr[Integer.parseInt(st.nextToken())];
        int p = Integer.parseInt(st.nextToken());
        int answer = 0;

        Queue<Integer> que = new LinkedList<Integer>();
        dp[s] = indegree[s];
        que.add(s);

        while (!que.isEmpty()) {
            int now = que.poll();
            for (int next : scc[now]) {
                if (dp[next] < dp[now] + indegree[next]) {
                    dp[next] = dp[now] + indegree[next];
                    que.add(next);
                }
            }
        }

        st = new StringTokenizer(br.readLine());
        while (p-- > 0)
            answer = Math.max(answer, dp[scc_arr[Integer.parseInt(st.nextToken())]]);
        bw.write(answer + "\n");

        bw.flush();
        bw.close();
        br.close();
    }

    private static int SCC(int idx) {
        order[idx] = ++num;
        stack.add(idx);
        int root = order[idx];

        for (int next : edges[idx]) {
            if (order[next] == 0)
                root = Math.min(root, SCC(next));
            else if (!visit[next])
                root = Math.min(root, order[next]);
        }

        if (root == order[idx]) {
            while (true) {
                int top = stack.pop();
                scc_arr[top] = scc_total;
                visit[top] = true;
                if (top == idx)
                    break;
            }
            scc_total++;
        }
        return root;
    }
}

• Python

코사라주 알고리즘 이용 (역방향 그래프 이용)

import sys
from collections import deque
sys.setrecursionlimit(650001)
input = lambda: sys.stdin.readline().rstrip()
read = lambda: map(int, input().split())

def dfs(node):
    visit[node] = 1
    for now in graph[node]:
        if not visit[now]:
            dfs(now)
    stack.append(node)

def reverse_dfs(node, num):
    scc_num[node] = num
    scc_arr[num] += 1
    scc_val[num] += cash[node]
    for now in reverse_graph[node]:
        if scc_num[now] == -1:
            reverse_dfs(now, num)
        elif scc_num[node] != scc_num[now]:
            group[scc_num[now]].append(scc_num[node])

N, M = read()
graph = [[] for i in range(N)]
reverse_graph = [[] for i in range(N)]
visit = [0] * N
stack = []
scc_num = [-1] * N
scc_arr = []
group = []

for i in range(M):
    a, b = read()
    graph[a-1].append(b-1)
    reverse_graph[b-1].append(a-1)    

cash = [int(input()) for i in range(N)]

for i in range(N):
    if not visit[i]:
        dfs(i)

scc_val = []
k = 0
while stack:
    now = stack.pop()
    if scc_num[now] == -1:
        group.append([])
        scc_arr.append(0)
        scc_val.append(0)
        reverse_dfs(now, k)
        k += 1

S, P = read()
S -= 1
result = list(read())

del graph, reverse_graph

que = deque([scc_num[S]])
dp = [0] * k
dp[scc_num[S]] = scc_val[scc_num[S]]
while que:
    now = que.popleft()
    for n in group[now]:
        if dp[n] < dp[now] + scc_val[n]:
            dp[n] = dp[now] + scc_val[n]
            que.append(n)
answer = 0
for r in result:
    answer = max(answer, dp[scc_num[r-1]])
print(answer)

algorithm practice

- 단계별 문제풀기

37. 강한 연결 요소

Strongly connected component를 다뤄 봅시다.

3. 축구 전술

3977번

SCC를 사용하는 문제 2

이번 문제는 경기장을 여러 개의 구역으로 나누고, 어떤 선수가 A구역에서 B구역으로 이동하게 하는 움직임을 (A, B)로 표현한다고 할 때, 다른 모든 구역에 도달할 수 있는 시작 구역을 찾아내는 문제이다.

SCC를 찾는 알고리즘은 크게 이 두가지 방법이다.

• 타잔 알고리즘 모든 정점에 대해 DFS를 수행하여 SCC를 찾는 알고리즘으로, 코사라주 알고리즘에 비해 적용이 더 쉽다고 한다. ① 인접 정점에 방문하며 자기 자신을 스택에 넣고, 재귀적으로 DFS를 수행한다. ② 인접 정점에 방문했지만, 아직 처리중인 상태일 경우, 작은 값으로 부모값을 갱신한다. ③ 부모 노드의 DFS가 끝난 경우에는, 자신의 id값이 스택에서 나올 때까지 스택에 있는 노드들을 pop하고 scc 배열에 추가한다. ④ 만들어진 하나의 scc를 전체 SCC 배열에 추가한다. (구현이 더 어렵지만, 활용도는 더 높다고 한다.)
  

• 코사라주 알고리즘 주어진 방향 그래프의 역방향 그래프와 스택을 사용하여 SCC를 구하는 알고리즘이다. 방향, 역방향 그래프가 동일한 SCC를 구성한다는 것을 이용한 방법이다. ① 주어지는 방향 그래프와 그 그래프의 역방향 그래프를 만든다. ② 정점을 담을 스택을 만들고 임의의 정점부터 DFS를 수행한다. ③ DFS가 끝나는 순서대로 스택에 삽입하고, 아직 방문하지 않은 정점에 대해 DFS를 수행한다. ④ 모든 정점이 스택에 담긴 후에는 스택을 pop하여 나오는 정점부터 역방향 그래프에서 DFS를 수행한다.. 이미 방문한 정점은 pop만 시행한다. ⑤ 이때 탐색되는 모든 정점을 SCC로 묶는다. 이것을 스택이 빌 때까지 진행한다. (타잔 알고리즘에 비해 구현이 더 쉬운 편이라고 한다.)

저번 SCC 문제들과 유사하고, 조금만 변형해서 풀 수 있었다.

Java / Python

• Java

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

public class Main {
    static int scc_total, num;
    static ArrayList<Integer>[] edges;
    static int[] order, scc_arr;
    static boolean[] visit; // SCC 확정된 정점 확인
    static Stack<Integer> stack;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        for (int t = 0; t < T; t++) {
            if (t != 0) {
                br.readLine();
            }

            st = new StringTokenizer(br.readLine());

            int N = Integer.parseInt(st.nextToken()); // 정점의 개수
            int M = Integer.parseInt(st.nextToken()); // 간선의 개수

            edges = new ArrayList[N + 1];

            for (int i = 0; i < N + 1; i++) {
                edges[i] = new ArrayList<>();
            }

            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());

                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                edges[a].add(b);
            }

            scc_arr = new int[N + 1];
            order = new int[N + 1];
            visit = new boolean[N + 1];
            scc_total = num = 0;
            stack = new Stack<>();

            for (int i = 0; i < N; i++) {
                if (order[i] == 0)
                    SCC(i);
            }

            int[] indegree = new int[scc_total];

            for (int i = 0; i < N; i++) {
                int s = edges[i].size();

                for (int j = 0; j < s; j++) {
                    int end = edges[i].get(j);

                    if (scc_arr[end] != scc_arr[i])
                        indegree[scc_arr[end]]++;
                }

            }
            int cnt = 0;
            int tag = 0;

            for (int i = 0; i < scc_total; i++) {
                if (indegree[i] == 0) {
                    tag = i;
                    cnt++;
                }
            }

            if (cnt > 1)
                bw.write("Confused\n");
            else {
                for (int i = 0; i < N; i++) {
                    if (scc_arr[i] == tag)
                        bw.write(i + "\n");
                }
            }
            bw.write("\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    private static int SCC(int idx) {
        order[idx] = ++num;
        stack.add(idx);
        int root = order[idx];

        for (int i = 0; i < edges[idx].size(); i++) {
            int temp = edges[idx].get(i);
            if (order[temp] == 0)
                root = Math.min(root, SCC(temp));
            else if (!visit[temp])
                root = Math.min(root, order[temp]);
        }

        if (root == order[idx]) {
            while (true) {
                int top = stack.pop();
                scc_arr[top] = scc_total;
                visit[top] = true;
                if (top == idx)
                    break;
            }
            scc_total++;
        }
        return root;
    }
}

• Python

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# 정방향 dfs, dfs 가 종료되는 노드를 stack에.
def dfs(node, visit, stack):
    visit[node] = 1
    for now in graph[node]:
        if visit[now] == 0:
            dfs(now, visit, stack)
    stack.append(node)

# 역방향 dfs, 탐색하는 순서대로 stack에.
def reverse_dfs(node, visit, stack):
    visit[node] = 1
    ids[node] = idx
    stack.append(node)
    for now in reverse_graph[node]:
        if visit[now] == 0:
            reverse_dfs(now, visit, stack)

T = int(input())
while T:
    inline = input()
    if inline == '\n':
        continue
    N, M = map(int, inline.split())
    graph = [[] for _ in range(N)]
    reverse_graph = [[] for _ in range(N)]

    for _ in range(M):
        a, b = map(int, input().split())
        # 정방향 그래프, 역방향 그래프 추가
        graph[a].append(b)
        reverse_graph[b].append(a)
    stack = []
    visit = [0] * N
    # 모든 노드에서 dfs를 수행.
    for i in range(N):
        if visit[i] == 0:
            dfs(i, visit, stack)

    result = [[] for _ in range(N)]
    visit = [0] * N
    idx = -1
    ids = [-1] * N

    while stack:
        # pop되는 요소에서 역방향 dfs, scc를 결과에.
        ssc = []
        node = stack.pop()
        if visit[node] == 0:
            idx += 1
            reverse_dfs(node, visit, ssc)
            result[idx] = ssc
    scc_indegree = [0] * (idx + 1)

    for i in range(N):
        for ed in graph[i]:
            if ids[i] != ids[ed]:
                scc_indegree[ids[ed]] += 1
    cnt = 0
    temp = []
    for i in range(len(scc_indegree)):
        if scc_indegree[i] == 0:
            for r in result[i]:
                temp.append(r)
            cnt += 1
    if cnt == 1:
        for i in sorted(temp):
            print(i)
    else:
        print("Confused")
    print()
    T -= 1

algorithm practice

- 단계별 문제풀기

37. 강한 연결 요소

Strongly connected component를 다뤄 봅시다.

2. 도미노

4196번

SCC를 사용하는 문제 1

이번 문제는 이제 각 도미노 블록의 배치가 주어졌을 때, 모든 블록을 넘어뜨리기 위해 손으로 넘어뜨려야 하는 블록 개수의 최솟값을 구하는 문제이다.

SCC를 찾는 알고리즘은 크게 이 두가지 방법이다.

• 타잔 알고리즘 모든 정점에 대해 DFS를 수행하여 SCC를 찾는 알고리즘으로, 코사라주 알고리즘에 비해 적용이 더 쉽다고 한다. ① 인접 정점에 방문하며 자기 자신을 스택에 넣고, 재귀적으로 DFS를 수행한다. ② 인접 정점에 방문했지만, 아직 처리중인 상태일 경우, 작은 값으로 부모값을 갱신한다. ③ 부모 노드의 DFS가 끝난 경우에는, 자신의 id값이 스택에서 나올 때까지 스택에 있는 노드들을 pop하고 scc 배열에 추가한다. ④ 만들어진 하나의 scc를 전체 SCC 배열에 추가한다. (구현이 더 어렵지만, 활용도는 더 높다고 한다.)
  

• 코사라주 알고리즘 주어진 방향 그래프의 역방향 그래프와 스택을 사용하여 SCC를 구하는 알고리즘이다. 방향, 역방향 그래프가 동일한 SCC를 구성한다는 것을 이용한 방법이다. ① 주어지는 방향 그래프와 그 그래프의 역방향 그래프를 만든다. ② 정점을 담을 스택을 만들고 임의의 정점부터 DFS를 수행한다. ③ DFS가 끝나는 순서대로 스택에 삽입하고, 아직 방문하지 않은 정점에 대해 DFS를 수행한다. ④ 모든 정점이 스택에 담긴 후에는 스택을 pop하여 나오는 정점부터 역방향 그래프에서 DFS를 수행한다.. 이미 방문한 정점은 pop만 시행한다. ⑤ 이때 탐색되는 모든 정점을 SCC로 묶는다. 이것을 스택이 빌 때까지 진행한다. (타잔 알고리즘에 비해 구현이 더 쉬운 편이라고 한다.)

다음에 더 자세히 정리해봐야 겠다..

Java / Python

• Java

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

public class Main {
    static int size, num;
    static ArrayList<Integer>[] graph, result;
    static int[] order, scc_arr;
    static boolean[] visit; // SCC 확정된 정점 확인
    static Stack<Integer> stack;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());

            int N = Integer.parseInt(st.nextToken()); // 정점의 개수
            int M = Integer.parseInt(st.nextToken()); // 간선의 개수

            graph = new ArrayList[N + 1];
            result = new ArrayList[N + 1];

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

            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());

                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());

                graph[x].add(y);
            }

            scc_arr = new int[N + 1];
            order = new int[N + 1];
            visit = new boolean[N + 1];
            size = num = 0;
            stack = new Stack<>();

            for (int i = 1; i < N + 1; i++) {
                if (order[i] == 0)
                    SCC(i);
            }

            boolean[] indegree = new boolean[size];

            for (int i = 1; i < N + 1; i++) {
                int s = graph[i].size();

                for (int j = 0; j < s; j++) {
                    int end = graph[i].get(j);

                    if (scc_arr[end] != scc_arr[i])
                        indegree[scc_arr[end]] = true;
                }

            }
            int cnt = 0;
            for (int i = 0; i < size; i++) {
                if (!indegree[i])
                    cnt++;
            }
            bw.write(cnt + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    private static int SCC(int idx) {
        order[idx] = ++num;
        stack.add(idx);
        int root = order[idx];

        for (int i = 0; i < graph[idx].size(); i++) {
            int temp = graph[idx].get(i);
            if (order[temp] == 0)
                root = Math.min(root, SCC(temp));
            else if (!visit[temp])
                root = Math.min(root, order[temp]);
        }

        if (root == order[idx]) {
            while (true) {
                int top = stack.pop();
                result[size].add(top);
                scc_arr[top] = size;
                visit[top] = true;
                if (top == idx)
                    break;
            }
            size++;
        }
        return root;
    }
}

• Python

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# 정방향 dfs, dfs 가 종료되는 노드를 stack에.
def dfs(node, visit, stack):
    visit[node] = 1
    for now in graph[node]:
        if visit[now] == 0:
            dfs(now, visit, stack)
    stack.append(node)

# 역방향 dfs, 탐색하는 순서대로 stack에.
def reverse_dfs(node, visit, stack):
    visit[node] = 1
    ids[node] = idx
    stack.append(node)
    for now in reverse_graph[node]:
        if visit[now] == 0:
            reverse_dfs(now, visit, stack)

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    reverse_graph = [[] for _ in range(N + 1)]

    for _ in range(M):
        x, y = map(int, input().split())
        # 정방향 그래프, 역방향 그래프 추가
        graph[x].append(y)
        reverse_graph[y].append(x)
    stack = []
    visit = [0] * (N + 1)
    # 모든 노드에서 dfs를 수행.
    for i in range(1, N + 1):
        if visit[i] == 0:
            dfs(i, visit, stack)
    idx = 0
    ids = [-1] * (N + 1)
    visit = [0] * (N + 1)
    result = []
    while stack:
        # pop되는 요소에서 역방향 dfs, scc를 결과에.
        ssc = []
        node = stack.pop()
        if visit[node] == 0:
            idx += 1
            reverse_dfs(node, visit, ssc)
            result.append(sorted(ssc))
    scc_indegree = [0] * (idx + 1)

    for i in range(1, N + 1):
        for ed in graph[i]:
            if ids[i] != ids[ed]:
                scc_indegree[ids[ed]] += 1
    cnt = 0
    for i in range(1, len(scc_indegree)):
        if scc_indegree[i] == 0:
            cnt += 1
    print(cnt)

algorithm practice

- 단계별 문제풀기

37. 강한 연결 요소

Strongly connected component를 다뤄 봅시다.

1. Strongly Connected Component

2150번

Strongly connected component를 만들어 봅시다.

이번 문제는 방향 그래프가 주어졌을 때, 그 그래프를 SCC(Strongly Connected Component)들로 나누는 프로그램을 작성하는 문제이다. (방향 그래프의 SCC는 우선 정점의 최대 부분집합이며, 그 부분집합에 들어있는 서로 다른 임의의 두 정점 u, v에 대해서 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재하는 경우를 말한다.)

SCC를 찾는 알고리즘은 크게 이 두가지 방법이다.

• 타잔 알고리즘 모든 정점에 대해 DFS를 수행하여 SCC를 찾는 알고리즘으로, 코사라주 알고리즘에 비해 적용이 더 쉽다고 한다. ① 인접 정점에 방문하며 자기 자신을 스택에 넣고, 재귀적으로 DFS를 수행한다. ② 인접 정점에 방문했지만, 아직 처리중인 상태일 경우, 작은 값으로 부모값을 갱신한다. ③ 부모 노드의 DFS가 끝난 경우에는, 자신의 id값이 스택에서 나올 때까지 스택에 있는 노드들을 pop하고 scc 배열에 추가한다. ④ 만들어진 하나의 scc를 전체 SCC 배열에 추가한다. (구현이 더 어렵지만, 활용도는 더 높다고 한다.)
  

• 코사라주 알고리즘 주어진 방향 그래프의 역방향 그래프와 스택을 사용하여 SCC를 구하는 알고리즘이다. 방향, 역방향 그래프가 동일한 SCC를 구성한다는 것을 이용한 방법이다. ① 주어지는 방향 그래프와 그 그래프의 역방향 그래프를 만든다. ② 정점을 담을 스택을 만들고 임의의 정점부터 DFS를 수행한다. ③ DFS가 끝나는 순서대로 스택에 삽입하고, 아직 방문하지 않은 정점에 대해 DFS를 수행한다. ④ 모든 정점이 스택에 담긴 후에는 스택을 pop하여 나오는 정점부터 역방향 그래프에서 DFS를 수행한다.. 이미 방문한 정점은 pop만 시행한다. ⑤ 이때 탐색되는 모든 정점을 SCC로 묶는다. 이것을 스택이 빌 때까지 진행한다. (타잔 알고리즘에 비해 구현이 더 쉬운 편이라고 한다.)

다음에 더 자세히 정리해봐야 겠다..

Java / Python

• Java

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

public class Main {
    static int V, E, size, num;
    static ArrayList<Integer>[] graph, result;
    static int[] order;
    static boolean[] visit; // SCC 확정된 정점 확인
    static Stack<Integer> stack;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        V = Integer.parseInt(st.nextToken()); // 정점의 개수
        E = Integer.parseInt(st.nextToken()); // 간선의 개수

        graph = new ArrayList[V + 1];
        result = new ArrayList[V + 1];

        for (int i = 0; i < V + 1; i++) {
            graph[i] = new ArrayList<>();
            result[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);
        }

        order = new int[V + 1];
        visit = new boolean[V + 1];
        size = 0;
        num = 0;
        stack = new Stack<>();

        for (int i = 1; i < V + 1; i++) {
            if (order[i] == 0)
                SCC(i);
        }
        sb.append(size + "\n");

        for (int i = 0; i < V + 1; i++) {
            int s = result[i].size();
            // 2^K 번째 조상 노드 저장
            if (s > 0) {
                for (int j = 0; j < s; j++) {
                    sb.append(result[i].get(j) + " ");
                }
                sb.append("-1\n");
            }
        }
        bw.write(sb.toString());

        bw.flush();
        bw.close();
        br.close();
    }

    private static int SCC(int idx) {
        order[idx] = ++num;
        stack.add(idx);
        int root = order[idx];

        for (int i = 0; i < graph[idx].size(); i++) {
            int temp = graph[idx].get(i);
            if (order[temp] == 0)
                root = Math.min(root, SCC(temp));
            else if (!visit[temp])
                root = Math.min(root, order[temp]);
        }

        if (root == order[idx]) {
            ArrayList<Integer> tempArr = new ArrayList<>();
            while (true) {
                int top = stack.pop();
                tempArr.add(top);
                visit[top] = true;
                if (top == idx)
                    break;
            }
            Collections.sort(tempArr);
            int min = Collections.min(tempArr);
            result[min] = tempArr;
            size++;
        }
        return root;
    }
}

• Python

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

V, E = map(int, input().split())
graph = [[] for _ in range(V + 1)]
reverse_graph = [[] for _ in range(V + 1)]
for _ in range(E):
    a, b = map(int, input().split())
    # 정방향 그래프, 역방향 그래프 추가
    graph[a].append(b)
    reverse_graph[b].append(a)

# 정방향 dfs, dfs 가 종료되는 노드를 stack에.
def dfs(node, visit, stack):
    visit[node] = 1
    for now in graph[node]:
        if visit[now] == 0:
            dfs(now, visit, stack)
    stack.append(node)

# 역방향 dfs, 탐색하는 순서대로 stack에.
def reverse_dfs(node, visit, stack):
    visit[node] = 1
    stack.append(node)
    for now in reverse_graph[node]:
        if visit[now] == 0:
            reverse_dfs(now, visit, stack)

stack = []
visit = [0] * (V + 1)
# 모든 노드에서 dfs를 수행.
for i in range(1, V + 1):
    if visit[i] == 0:
        dfs(i, visit, stack)
visit = [0] * (V + 1)
result = []
while stack:
    # pop되는 요소에서 역방향 dfs, scc를 결과에.
    ssc = []
    node = stack.pop()
    if visit[node] == 0:
        reverse_dfs(node, visit, ssc)
        result.append(sorted(ssc))

print(len(result))
answer = sorted(result)
for i in answer:
    print(*i, -1)

algorithm practice

- 단계별 문제풀기

36. 최소 공통 조상

트리에서 두 정점의 최소 공통 조상을 구하는 자료구조를 배워 봅시다.

5. 트리와 쿼리 2

13511번

트리 상의 경로에서 k번째 정점을 구하는 문제

이번 문제는 N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 두 쿼리를 수행하는 프로그램을 작성하는 문제이다.

1 u v: u에서 v로 가는 경로의 비용을 출력한다. 2 u v k: u에서 v로 가는 경로에 존재하는 정점 중에서 k번째 정점을 출력한다. k는 u에서 v로 가는 경로에 포함된 정점의 수보다 작거나 같다.

dfs와 LCA를 이용해서, 이전 LCA 문제와 비슷한 방식으로 구할 수 있다. 조건을 나누어 거리(간선 비용)를 구한다.

Java : LCA함수와 parent를 이용해 조상을 구하고, dfs를 통해 depth를 확인하고 dist를 구한다.
Python : parent를 이용해 각 노드의 부모 노드 및 depth 계산하고, dp를 이용해 희소 테이블을 초기화 및 희소 테이블을 계산해주고, 조건을 나누어 거리를 구할 수 있다.

Java / Python

• Java

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

public class Main {

    static int N, M; // N : 정점수, M : 쿼리 수

    static int[] depth;
    static long[] dist;
    static int[][] parent; // parent[j][i] = parent[parent[j][i - 1]][i - 1];
    static ArrayList<Node>[] tree;

    static class Node {
        int target, cost;

        public Node(int target, int cost) {
            this.target = target;
            this.cost = cost;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());

        depth = new int[N + 1];
        dist = new long[N + 1];
        parent = new int[N + 1][18];
        tree = new ArrayList[N + 1];

        for (int i = 1; i < N + 1; i++) {
            tree[i] = new ArrayList<Node>();
        }

        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            tree[a].add(new Node(b, c));
            tree[b].add(new Node(a, c));
        }

        DFS(1, 1);

        // parent 채우기
        for (int i = 1; i < 18; i++) {
            for (int j = 2; j <= N; j++) {
                parent[j][i] = parent[parent[j][i - 1]][i - 1];
            }
        }

        // LCA
        M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {

            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int root = LCA(u, v);
            if (a == 1) {
                sb.append(dist[u] + dist[v] - 2 * dist[root] + "\n");
            } else {
                int k = Integer.parseInt(st.nextToken());
                int cnt = depth[u] - depth[root] + 1;
                if (cnt == k)
                    sb.append(root + "\n");
                else if (cnt > k) {
                    k--;
                    int tmp = u;
                    for (int j = 0; j < 18; j++) {
                        if ((k & 1 << j) != 0) {
                            k -= 1 << j;
                            tmp = parent[tmp][j];
                        }
                    }
                    sb.append(tmp + "\n");
                } else {
                    k = cnt + depth[v] - depth[root] - k + 1;
                    k--;
                    int tmp = v;
                    for (int j = 0; j < 18; j++) {
                        if ((k & 1 << j) != 0) {
                            k -= 1 << j;
                            tmp = parent[tmp][j];
                        }
                    }
                    sb.append(tmp + "\n");
                }
            }
        }
        bw.write(sb.toString());

        bw.flush();
        bw.close();
        br.close();
    }

    // depth 확인
    // dist 추가
    static void DFS(int node, int cur) {
        depth[node] = cur;

        for (Node next : tree[node]) {
            if (depth[next.target] == 0) {
                parent[next.target][0] = node;
                dist[next.target] = dist[node] + next.cost;
                DFS(next.target, cur + 1);
            }
        }
        return;
    }

    static int LCA(int a, int b) {
        if (depth[a] < depth[b]) {
            // a가 더 얕으면 swap
            int temp = a;
            a = b;
            b = temp;
        }
        for (int i = 18; i >= 0; i--) {
            if (Math.pow(2, i) <= depth[a] - depth[b]) {
                a = parent[a][i]; // 높이 차이 만큼 a 높이 올리기
            }
        }
        if (a == b) return a;

        for (int i = 17; i >= 0; i--) {
            if (parent[a][i] != parent[b][i]) { 
                a = parent[a][i];
                b = parent[b][i];
            }
        }
        return parent[a][0];
    }
}

• Python

import sys
from collections import deque
from math import log2
input = sys.stdin.readline

# tree 입력, 정렬, 부모노드, depth 계산 부분 
N = int(input())
tree = [[] for _ in range(N + 1)]

for _ in range(N - 1):
    a, b, c = map(int, input().split())
    tree[a].append([b, c])
    tree[b].append([a, c])

parent = [[0, 0] for _ in range(N + 1)]
depth = [0] * (N + 1)
visit = [False] * (N + 1)
que = deque([1])
visit[1] = True

while que:
    now = que.popleft()
    for b, c in tree[now]:
        if not visit[b]:
            que.append(b)
            parent[b][0] = now
            parent[b][1] = c
            depth[b] = depth[now] + 1
            visit[b] = True

# 희소 테이블
logN = int(log2(N) + 1)
dp = [[[0, 0] for _ in range(logN)] for __ in range(N + 1)]

for i in range(N + 1):
    dp[i][0][0] = parent[i][0]
    dp[i][0][1] = parent[i][1]

for j in range(1, logN):
    for i in range(1, N + 1):
        dp[i][j][0] = dp[dp[i][j - 1][0]][j - 1][0]
        dp[i][j][1] = dp[i][j - 1][1] + dp[dp[i][j - 1][0]][j - 1][1] 

# 쿼리문 입력, 처리 
M = int(sys.stdin.readline())
for _ in range(M):
    Query = list(map(int, input().split()))
    u, v = Query[1], Query[2]
    u2, v2 = u, v
    # 공통 조상 탐색 
    if depth[u2] < depth[v2]:
        u2, v2 = v2, u2
    diff = depth[u2] - depth[v2]
    for i in range(logN):
        if diff & 1 << i:
            u2 = dp[u2][i][0]
    if u2 == v2:
        lca = u2
    else:
        for i in range(logN - 1, -1, -1):
            if dp[u2][i][0] != dp[v2][i][0]:
                u2 = dp[u2][i][0]
                v2 = dp[v2][i][0]
        lca = dp[u2][0][0]
    if Query[0] == 1:
        cost = 0
        diff_u = depth[u] - depth[lca]
        diff_v = depth[v] - depth[lca]
        for i in range(logN):
            if diff_u & 1 << i:
                cost += dp[u][i][1]
                u = dp[u][i][0]
            if diff_v & 1 << i:
                cost += dp[v][i][1]
                v = dp[v][i][0]
        print(cost)
    else: 
        k = Query[3]
        # u 의 k - 1 조상을 계산
        if k <= depth[u] - depth[lca]: 
            diff = k - 1
            for i in range(logN):
                if diff & 1 << i:
                    u = dp[u][i][0]
            print(u)
        else: # 남은 거리를 v부터 계산
            diff = depth[v] + depth[u] - 2 * depth[lca] - k + 1
            for i in range(logN - 1, -1, -1):
                if diff & 1 << i:
                    v = dp[v][i][0]
            print(v)

algorithm practice

- 단계별 문제풀기

36. 최소 공통 조상

트리에서 두 정점의 최소 공통 조상을 구하는 자료구조를 배워 봅시다.

4. 도로 네트워크

3176번

트리 상의 경로에서 최솟값과 최댓값을 찾는 문제

이번 문제는 모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어지고 총 K개의 도시 쌍이 주어질 때, 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구하는 문제이다.

Java / Python

• Java

dfs와 LCA를 이용해서, 공통 조상을 구하며, 최소 거리와 최대 거리를 계산한다.

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

public class Main {

    static int N, K, k; // N : 정점수, k : 쿼리 수, k: 2의 지수

    static int[] depth;
    static int[][] parent; // parent[j][i] = parent[parent[j][i - 1]][i - 1];
    static ArrayList<Node>[] tree;

    // 도로 네트워크 변수
    // min(max)Dist[k][V] 정점 V의 2^K번째 조상까지의
    static int[][] minDist; // 최소거리
    static int[][] maxDist; // 최대거리

    static int min, max;

    static class Node {
        int target, cost;

        public Node(int target, int cost) {
            this.target = target;
            this.cost = cost;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());

        k = 0;
        for (int i = 1; i <= N; i *= 2) {
            k++;
        }

        depth = new int[N + 1];
        parent = new int[N + 1][k];

        minDist = new int[N + 1][k];
        maxDist = new int[N + 1][k];

        tree = new ArrayList[N + 1];
        for (int i = 1; i < N + 1; i++) {
            tree[i] = new ArrayList<Node>();
        }

        int a, b, c;
        for (int i = 1; i <= N - 1; i++) {
            st = new StringTokenizer(br.readLine());

            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            tree[a].add(new Node(b, c));
            tree[b].add(new Node(a, c));
        }

        DFS(1, 1);

        // parent 채우기 
        for (int i = 1; i < k; i++) {
            for (int j = 1; j <= N; j++) {
                parent[j][i] = parent[parent[j][i - 1]][i - 1];

                minDist[j][i] = Math.min(minDist[j][i - 1], minDist[parent[j][i - 1]][i - 1]);
                maxDist[j][i] = Math.max(maxDist[j][i - 1], maxDist[parent[j][i - 1]][i - 1]);
            }
        }

        // LCA
        K = Integer.parseInt(br.readLine());

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

            LCA(a, b);
            sb.append(min + " " + max + "\n");
        }

        bw.write(sb.toString());

        bw.flush();
        bw.close();
        br.close();
    }

    // depth 확인
    static void DFS(int node, int cur) {
        depth[node] = cur;

        for (Node next : tree[node]) {
            if (depth[next.target] == 0) {
                DFS(next.target, cur + 1);
                parent[next.target][0] = node;

                // 현재 cost로 갱신
                minDist[next.target][0] = next.cost;
                maxDist[next.target][0] = next.cost;
            }
        }
        return;
    }

    static void LCA(int a, int b) {
        if (depth[a] < depth[b]) {
            // a가 더 얕으면 swap
            int temp = a;
            a = b;
            b = temp;
        }

        min = Integer.MAX_VALUE;
        max = -1;

        for (int i = k - 1; i >= 0; i--) {
            if (Math.pow(2, i) <= depth[a] - depth[b]) {
                min = Math.min(min, minDist[a][i]);
                max = Math.max(max, maxDist[a][i]);

                a = parent[a][i]; // 높이 차이 만큼 a 높이 올리기
            }
        }

        if (a == b)
            return;

        for (int i = k - 1; i >= 0; i--) {
            if (parent[a][i] != parent[b][i]) {
                min = Math.min(min, Math.min(minDist[a][i], minDist[b][i]));
                max = Math.max(max, Math.max(maxDist[a][i], maxDist[b][i]));

                a = parent[a][i];
                b = parent[b][i];
            }
        }

        min = Math.min(min, Math.min(minDist[a][0], minDist[b][0]));
        max = Math.max(max, Math.max(maxDist[a][0], maxDist[b][0]));

        return;
    }
}

• Python

dp를 이용해 (3차원 배열 이용 [0]: parent, [1]: minLength, [2]: maxLength) 초기화 및 희소 테이블을 계산해주고, 두 도시 사이의 거리를 구할 수 있다.

import sys
import math
from collections import deque
input = sys.stdin.readline

N = int(input())
K = int(math.log2(N))+1
tree = [[] for _ in range(N + 1)]

for i in range(N - 1):
    a, b, w = map(int, input().split())
    tree[a].append((b,w))
    tree[b].append((a,w))

queue = deque([(1, 1)])
depth = [0] * (N + 1)
depth[1] = 1
dp = [[[0,0,0] for _ in range(K)] for _ in range(N+1)]

while queue:
    i, d = queue.popleft()
    for j, w in tree[i]:
        if not depth[j]:
            queue.append((j, d + 1))
            depth[j] = d + 1
            dp[j][0] = [i,w,w]

for j in range(1, K):
    for i in range(1, N + 1):
        dp[i][j][0] = dp[dp[i][j-1][0]][j-1][0]
        dp[i][j][1] = min(dp[i][j-1][1], dp[dp[i][j-1][0]][j-1][1])
        dp[i][j][2] = max(dp[i][j-1][2], dp[dp[i][j-1][0]][j-1][2])

for _ in range(int(input())):
    a, b = map(int, input().split())
    max_len = 0
    min_len = float('inf')

    if depth[a] > depth[b]:
        a, b = b, a
    for i in range(K, -1, -1):
        if depth[b] - depth[a] >= (1<<i):
            min_len = min(dp[b][i][1], min_len)
            max_len = max(dp[b][i][2], max_len)
            b = dp[b][i][0]
    if a == b:
        print(min_len, max_len)
        continue

    for i in range(K-1, -1, -1):
        if dp[a][i][0] != dp[b][i][0]:
            min_len = min(dp[a][i][1],dp[b][i][1], min_len)
            max_len = max(dp[a][i][2],dp[b][i][2], max_len)
            a = dp[a][i][0]
            b = dp[b][i][0]
    min_len = min(dp[a][0][1],dp[b][0][1], min_len)
    max_len = max(dp[a][0][2],dp[b][0][2], max_len)
    print(min_len, max_len)

algorithm practice

- 단계별 문제풀기

36. 최소 공통 조상

트리에서 두 정점의 최소 공통 조상을 구하는 자료구조를 배워 봅시다.

3. LCA 2

11438번

LCA를 효율적으로 구해 봅시다.

이번 문제는 두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력하는 문제이다.

1. dfs를 통해서 자신의 부모를 구한다.
2. 이중 for문을 통해서 조상을 세팅한다.

• parent[j][i-1] = j의 2^i-1만큼 위에 있는 조상

3. 두 노드의 가장 가까운 조상(부모) 출력 (LCA알고리즘)

• swap (a가 더 얕으면 swap)
• 두 노드 높이를 맞춤
• 같은 높이일 경우, 두 노드의 값이 같으면 종료
• 같은 높이일 경우, 두 노드의 값이 다르면 두 노드의 높이를 올려가며 확인

Java / Python

• Java

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

public class Main {
    private static int N, M, K;
    private static int[] depth;
    private static int[][] parent;
    private static ArrayList<Integer>[] list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());

        list = new ArrayList[N + 1];
        for (int i = 0; i < N + 1; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

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

        K = 0;
        int tmp = 1;
        while (tmp < N + 1) {
            tmp <<= 1;
            K++;
        }

        depth = new int[N + 1];
        parent = new int[N + 1][K];

        dfs(1, 1);
        for (int i = 1; i < K; i++) {
            // 2^K 번째 조상 노드 저장
            for (int j = 1; j <= N; j++) {
                parent[j][i] = parent[parent[j][i - 1]][i - 1];
            }
        }

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

            sb.append(LCA(a, b)).append("\n");
        }

        bw.write(sb.toString() + "\n");

        bw.flush();
        bw.close();
        br.close();
    }

    private static void dfs(int node, int cur) {
        depth[node] = cur;
        for (Integer next : list[node]) {
            if (depth[next] == 0) {
                dfs(next, cur + 1);
                parent[next][0] = node;
            }
        }
    }

    private static int LCA(int a, int b) {
        if (depth[a] < depth[b]) {
            // a가 더 얕으면 swap
            int temp = a;
            a = b;
            b = temp;
        }

        for (int i = K - 1; i >= 0; i--) {
            if (Math.pow(2, i) <= depth[a] - depth[b]) {
                // 높이 차이 만큼 a 높이 올리기 
                a = parent[a][i];
            }
        }

        if (a == b)
            return a;

        for (int i = K - 1; i >= 0; i--) {
            if (parent[a][i] != parent[b][i]) {
                a = parent[a][i];
                b = parent[b][i];
            }
        }
        return parent[a][0];
    }
}

• Python

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
LOG = 21
# 2^i 단위의 부모값을 저장하기 위한 크기

N = int(input())
parent = [[0] * LOG for _ in range(N + 1)]
visit = [False] * (N + 1)
depth = [0] * (N + 1)
tree = [[] for _ in range(N + 1)]

for _ in range(N - 1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

def dfs(cur, d):
    visit[cur] = True
    depth[cur] = d
    for node in tree[cur]:
        if not visit[node]:
            parent[node][0] = cur
            dfs(node, d + 1)

def lca(a, b):
    if depth[a] > depth[b]:
        a, b = b, a

    # a와 b의 깊이 동일하게
    for i in range(LOG - 1, -1, -1):
        if depth[b] - depth[a] >= (1<<i):
            b = parent[b][i]

    if a == b:
        return a

    # 올라가면서 공통 조상 찾기
    for i in range(LOG - 1, -1, -1):
        if parent[a][i] != parent[b][i]:
            a = parent[a][i]
            b = parent[b][i]

    return parent[a][0]

dfs(1, 0)
# 모든 노드의 전체 부모 관계 갱신
for i in range(1, LOG):
    for j in range(1, N + 1):
        # 각 노드에 대해 2^i번째 부모 정보 갱신
        parent[j][i] = parent[parent[j][i - 1]][i - 1]

M = int(input())

for _ in range(M):
    a, b = map(int, input().split())
    print(lca(a, b))

algorithm practice

- 단계별 문제풀기

36. 최소 공통 조상

트리에서 두 정점의 최소 공통 조상을 구하는 자료구조를 배워 봅시다.

2. 합성함수와 쿼리

17435번

효율적인 LCA 구현을 위해 필요한 sparse table 자료구조를 배워 봅시다.

이번 문제는 n과 x가 주어질 때 fn(x)를 계산하는 쿼리를 수행하는 프로그램을 작성하는 문제이다.

Sparse table이란? 조건 1. array에 저장된 값이 변하지 않는다. 조건 2. f(a, b, c) = f(a, (b, c)) = f(f(a, b),c)로 결합 법칙이 성립한다. 위 조건을 만족할 때 쿼리를 O(lgN) 만에 처리할 수 있는 자료 구조이다. 전처리 과정을 통해 배열 내 구간의 쿼리를 빠르게 수행할 수 있도록 하는 자료구조라고 볼 수 있다. 2의 거듭제곱인 범위의 구간값을 미리 계산해 저장해놓고 이용하는 방식이다. 시간복잡도를 O(log n)까지 줄일 수 있다.

Java / Python

• Java

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

public class Main {
    private final static int log = 19;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int M = Integer.parseInt(br.readLine());
        int[][] dp = new int[log + 1][M + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < M + 1; i++) {
            dp[0][i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 1; i < log + 1; i++) {
            for (int j = 1; j < M + 1; j++) {
                dp[i][j] = dp[i - 1][dp[i - 1][j]];
            }
        }

        int Q = Integer.parseInt(br.readLine());
        while (Q-- > 0) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            for (int b = 0; b < log; b++) {
                if ((n & (1 << b)) > 0) {
                    x = dp[b][x];
                }
            }
            sb.append(x).append("\n");
        }

        bw.write(sb.toString() + "\n");

        bw.flush();
        bw.close();
        br.close();
    }
}

• Python

import sys
input = sys.stdin.readline

log = 18
M = int(input())
f = [0]+list(map(int,input().split()))
dp = [[f[i]] for i in range(M+1)]

for j in range(1, log + 1):
    for i in range(1, M + 1):
        dp[i].append(dp[dp[i][j-1]][j-1])

Q = int(input())
for _ in range(Q):
    n,x = map(int, input().split())
    for b in range(log, -1, -1):
        if n >= 1 << b:
            n -= 1<<b
            x = dp[x][b]
    print(x)

algorithm practice

- 단계별 문제풀기

36. 최소 공통 조상

트리에서 두 정점의 최소 공통 조상을 구하는 자료구조를 배워 봅시다.

1. 가장 가까운 공통 조상

3584번

LCA에 대해 알아 봅시다. 한 쌍의 LCA만 구하면 되므로 아직은 효율적인 구현이 필요하지 않습니다.

이번 문제는 루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 문제이다.

LCA란? Lowest Common Ancestor로, 최소 공통 조상을 찾는 알고리즘을 말하며, 트리상에서 어떤 두 정점 u, v가 있을 때, u이거나 u의 조상이면서 동시에 v이거나 v의 조상인 노드들 중 가장 깊은 노드를 찾는 것이다.

Java / Python

• Java

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

public class Main {
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            parent = new int[N + 1];
            ArrayList<Integer>[] list = new ArrayList[N + 1];

            for (int i = 0; i <= N; i++) {
                list[i] = new ArrayList<>();
            }

            for (int i = 0; i < N - 1; i++) {
                st = new StringTokenizer(br.readLine());

                int p = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());

                parent[c] = p;
                list[p].add(c);
            }
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            int u_depth = getDepth(u);
            int v_depth = getDepth(v);

            bw.write(LCA(u, u_depth, v, v_depth) + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    public static int getDepth(int i) {
        int cnt = 0;
        int now = i;
        while (now != 0) {
            cnt++;
            now = parent[now];
        }
        return cnt - 1;
    }

    public static int LCA(int x, int x_depth, int y, int y_depth) {
        // 깊이가 같아지게 한다.
        if (x_depth > y_depth) {
            while (x_depth != y_depth) {
                x_depth--;
                x = parent[x];
            }
        } else if (x_depth < y_depth) {
            while (x_depth != y_depth) {
                y_depth--;
                y = parent[y];
            }
        }
        while (x != y) {
            x = parent[x];
            y = parent[y];
        }

        return x;
    }
}

• Python

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    N = int(input())
    parent = [0 for _ in range(N+1)] # 각 노드의 부모노드 저장
    for _ in range(N-1):
        p,c = map(int,input().split())
        parent[c] = p # 부모 노드 저장

    u, v = map(int,input().split())
    u_p = [u]
    v_p = [v]

    while parent[u]:
        u_p.append(parent[u])
        u = parent[u]

    while parent[v]:
        v_p.append(parent[v])
        v = parent[v]

    # 같은 레벨로
    u_level = len(u_p)-1
    v_level = len(v_p)-1

    while u_p[u_level] == v_p[v_level]: # 부모 노드가 다를 때까지 
        u_level -= 1
        v_level -= 1

    print(u_p[u_level + 1])

algorithm practice

- 단계별 문제풀기

35. 위상 정렬

간선에 방향이 있는 그래프의 정점을 나열해 역방향이 없게 만드는 알고리즘을 다뤄 봅시다.

4. 문제집

1766번

위상정렬 알고리즘을 변형하여 사전순으로 가장 앞선 위상정렬을 찾는 문제

이번 문제는 문제의 개수와 먼저 푸는 것이 좋은 문제에 대한 정보가 주어졌을 때, 주어진 조건을 만족하면서 풀 문제의 순서를 결정해 주는 프로그램을 작성하는 문제이다.

순서가 정해져있는 작업을 차쳬로 수행할 때, 순서를 정해주는 문제로, 전형적인 위상 정렬 문제라고 할 수 있다. 먼저 풀어야 하는 문제와, 나중에 풀어야하는 문제를 분류하고 크기대로 정렬해주는 우선순위 큐를 사용해서 문제를 풀 수 있다.

Java / Python

• Java

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

public class Main {
    static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int[] indegree = new int[N + 1];
        ArrayList<Integer>[] list = new ArrayList[N + 1];

        for (int i = 0; i <= N; i++) {
            list[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            list[s].add(e);
            indegree[e]++;
        }

        bw.write(topologicalSort(indegree, list) + "\n");

        bw.flush();
        bw.close();
        br.close();
    }

    public static String topologicalSort(int[] indegree, ArrayList<Integer>[] list) {
        PriorityQueue<Integer> pque = new PriorityQueue<Integer>();
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < N + 1; i++) {
            if (indegree[i] == 0) {
                pque.offer(i);
            }
        }

        while (!pque.isEmpty()) {
            int node = pque.poll();
            for (int i : list[node]) {

                indegree[i]--;

                if (indegree[i] == 0)
                    pque.offer(i);
            }
            sb.append(node + " ");
        }
        return sb.toString();
    }
}

• Python

import sys
import heapq
input = sys.stdin.readline

N,M = map(int,input().split())
arr = [[] for _ in range(N+1)]
indegree=[0 for _ in range(N+1)]
heap = []
result = []

for _ in range(M): 
    s, e = map(int,input().split())
    arr[s].append(e)
    indegree[e]+=1

for i in range(1,N+1):
    if indegree[i] == 0:
        heapq.heappush(heap, i)

while heap:
    node = heapq.heappop(heap)
    result.append(node)
    for i in arr[node]:
        indegree[i]-=1 
        if indegree[i] == 0:
            heapq.heappush(heap, i)

for r in result:
    print(r , end=' ')

algorithm practice

- 단계별 문제풀기

35. 위상 정렬

간선에 방향이 있는 그래프의 정점을 나열해 역방향이 없게 만드는 알고리즘을 다뤄 봅시다.

3. ACM Craft

1005번

위상정렬된 순서대로 동적 계획법을 적용하는 문제

이번 문제는, 요약하면, 특정건물을 가장 빨리 지을 때까지 걸리는 최소시간을 알아내는 문제이다.

따라서 이번 문제의 경우 위상 정렬을 할 때, 소요 시간을 기억하고 이용해야 한다. 이전 건물이 다 올라가야 현재 건물을 지을 수 있기 때문에 이전 건물까지의 소요시간과 현재 건물의 소요시간을 더하여 오래 걸리는 값으로 result를 갱신해준다. 건물 W를 건설완료 하는데 드는 최소 시간(result[w])을 출력한다.

Java / Python

• Java

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

public class Main {

    static int N, K;
    static int[] time;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            time = new int[N + 1];

            ArrayList<Integer>[] list = new ArrayList[N];
            int[] indegree = new int[N + 1];
            st = new StringTokenizer(br.readLine());

            for (int i = 0; i < N; i++) {
                list[i] = new ArrayList<>();
                time[i] = Integer.parseInt(st.nextToken());
            }
            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine());

                int s = Integer.parseInt(st.nextToken());
                int e = Integer.parseInt(st.nextToken());

                list[s - 1].add(e - 1);
                indegree[e - 1]++;
            }

            int w = Integer.parseInt(br.readLine()); // 건물 번호 

            bw.write(topologicalSort(indegree, list, w) + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    public static int topologicalSort(int[] indegree, ArrayList<Integer>[] list, int w) {
        Queue<Integer> queue = new LinkedList<Integer>();
        int[] result = new int[N + 1];

        // 건물 기본 소요시간
        for (int i = 0; i < N; i++) {
            if (indegree[i] == 0) {
                result[i] = time[i];
                queue.offer(i);
            }
        }

        // 총 소요시간 = 이전 건물까지의 소요시간 + 현재 건물 소요시간
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int i : list[node]) {
                result[i] = Math.max(result[i], result[node] + time[i]);
                indegree[i]--;

                if (indegree[i] == 0)
                    queue.offer(i);
            }
        }
        return result[w - 1];
    }
}

• Python

import sys
from collections import deque
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    N,K = map(int,input().split())
    time = [0]+list(map(int,input().split())) # 건설 시간
    tree = [[] for _ in range(N+1)]
    indegree=[0 for _ in range(N+1)]
    dp = [0 for _ in range(N+1)] # 해당 건물까지 걸리는 시간

    for _ in range(K): # 입력값 받기
        s, e = map(int,input().split())
        tree[s].append(e)
        indegree[e]+=1

    que = deque()
    for i in range(1,N+1):
        if indegree[i] == 0:
            que.append(i)
            dp[i] = time[i]

    while que:
        node = que.popleft()
        for i in tree[node]:
            indegree[i]-=1
            dp[i] = max(dp[node] + time[i], dp[i]) 
            if indegree[i] == 0:
                que.append(i)

    w = int(input())
    print(dp[w])

algorithm practice

- 단계별 문제풀기

35. 위상 정렬

간선에 방향이 있는 그래프의 정점을 나열해 역방향이 없게 만드는 알고리즘을 다뤄 봅시다.

2. 최종 순위

3665번

간선을 직접 정의한 다음 위상정렬을 하는 문제

이번 문제는 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어졌을 때, 올해 순위를 만드는 프로그램을 작성하는 문제이다. (단, 본부에서 발표한 정보를 가지고 확실한 올해 순위를 만들 수 없는 경우가 있을 수도 있고, 일관성이 없는 잘못된 정보일 수도 있다. 이 두 경우도 모두 찾아내야 한다.)

위상정렬은 보통 A가 B보다 앞에 있는 경우인데, 이런 경우 단순하게 하나씩 관계를 보면 된다. 그런데 이번 문제는 순서가 미리 정해져 있으며, 순위의 앞뒤관계가 바뀌는 경우라 조금 더 복잡한 형태의 위상 정렬 문제라고 볼 수 있다. 따라서 이번 문제의 경우 순위에 따라, 모든 관계를 추가한다.
바뀐 순위들에 대해서 edge의 방향을 바꾸고 위상 정렬을 시행한다. 같은 진입 차수에 있어 순서를 구분할 수 없는 경우에는 "?"를, 데이터에 일관성이 없어서 순위를 정할 수 없는 경우에는 (주어지는 정보에서 사이클이 발생하는 경우)에는 "IMPOSSIBLE"을 출력한다.

Java / Python

• Java

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

public class Main {
    static int N;
    static int[] indegree;
    static boolean[][] edges;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            N = Integer.parseInt(br.readLine());
            indegree = new int[N + 1];
            edges = new boolean[N + 1][N + 1];

            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                int num = Integer.parseInt(st.nextToken());
                indegree[num] = i;

                for (int j = 1; j <= N; j++) {
                    if (j != num && !edges[j][num])
                        edges[num][j] = true;
                }
            }

            int M = Integer.parseInt(br.readLine());
            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int n1 = Integer.parseInt(st.nextToken());
                int n2 = Integer.parseInt(st.nextToken());
                swap(n1, n2);
            }
            bw.write(topologicalSort() + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    private static String topologicalSort() {
        Queue<Integer> queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();

        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0)
                queue.offer(i);
        }

        for (int i = 1; i <= N; i++) { // 정점 개수만큼 반복
            if (queue.size() == 0)
                return "IMPOSSIBLE";
            if (queue.size() > 1)
                return "?";
            int cur = queue.poll();
            sb.append(cur + " ");

            for (int j = 1; j <= N; j++) {
                if (edges[cur][j]) {
                    edges[cur][j] = false;
                    if (--indegree[j] == 0)
                        queue.offer(j);
                }
            }
        }
        return sb.toString();
    }

    private static void swap(int n1, int n2) {
        if (edges[n1][n2]) {
            edges[n1][n2] = false;
            edges[n2][n1] = true;
            indegree[n1]++;
            indegree[n2]--;

        } else {
            edges[n1][n2] = true;
            edges[n2][n1] = false;
            indegree[n1]--;
            indegree[n2]++;
        }
    }
}

• Python

import sys
from collections import deque

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    rank = list(map(int, sys.stdin.readline().split()))
    edges = [[False]*(n+1) for _ in range(n + 1)]
    indegree = [0] * (n + 1)

    for i in range(n):
        for j in range(i + 1, n):
            edges[rank[i]][rank[j]] = True

    m = int(sys.stdin.readline())
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        edges[a][b], edges[b][a] = edges[b][a], edges[a][b]

    que = deque()
    answer = []
    cnt = 0
    for i in range(1, n + 1):
        indegree[i] = edges[i].count(True)
        if indegree[i] == 0:
            cnt += 1
            que.append(i)

    if cnt != 1:
        if cnt > 1:
            print("?")
        elif cnt == 0:
            print("IMPOSSIBLE")
        continue

    while que and cnt == 1:
        cnt = 0
        cur = que.popleft()
        answer.append(cur)
        for i in range(1, n + 1):
            if edges[i][cur]:
                indegree[i] -= 1
                if indegree[i] == 0:
                    cnt += 1
                    que.append(i)

    if cnt > 1:
        print("?")
    elif len(answer) != n:
        print("IMPOSSIBLE")
    else:
        print(*answer[::-1])

algorithm practice

- 단계별 문제풀기

35. 위상 정렬

간선에 방향이 있는 그래프의 정점을 나열해 역방향이 없게 만드는 알고리즘을 다뤄 봅시다.

1. 줄 세우기

2252번

위상정렬을 배우는 문제

이번 문제는 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하는 문제이다.

노드 갯수 N, 간선 갯수 M 을 받은 후, 간선의 가중치를 입력받고 위상 정렬한다. 위상정렬 (Topological Sort) :'사이클'이 없고 '방향'만 존재하는 그래프(DAG: Directed Acyclic Graph)에서 정점(Vertex)을 나열하는 방법

1. 정점과 연결된 다른 정점 리스트, 정점에 들어오는 그래프 개수 리스트 2개를 만든다.
2. 진입 루트(Indegree)가 없는 정점을 먼저 큐에 넣는다.
3. 해당 정점과 연결되어있는 노드에서 진입 루트 개수를 하나씩 빼준다.
4. 큐를 출력하고 제거한다. (큐가 빌 때까지 반복한다.)

Java / Python

• Java

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        LinkedList<Integer>[] list = new LinkedList[N + 1];
        int[] indegree = new int[N + 1];

        for (int i = 0; i < N + 1; i++) {
            list[i] = new LinkedList<Integer>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            list[x].add(y);
            indegree[y]++;
        }

        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                queue.add(i);
            }
        }
        while (!queue.isEmpty()) {
            bw.write(queue.peek() + " ");
            int cur = queue.poll();

            for (int i = 0; i < list[cur].size(); i++) {
                int next = list[cur].get(i);
                indegree[next]--;
                if (indegree[next] == 0) {
                    queue.add(next);
                }
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

• Python

import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
arr = []
inDegree = [0 for i in range(32001)]
graph = [[] for i in range(32001)]

queue = deque()
for i in range(M):
    x, y = map(int, input().split())
    arr.append([x, y])

for a, b in arr:
    inDegree[b] += 1
    graph[a].append(b)

for i in range(1, N + 1):
    if inDegree[i] == 0:
        queue.append(i)

while queue:
    student = queue.popleft()
    print(student, end = ' ')
    for j in graph[student]:
        inDegree[j] -= 1
        if inDegree[j] == 0:
            queue.append(j)

algorithm practice

- 단계별 문제풀기

34. 문자열 알고리즘 1

KMP 알고리즘과 트라이 자료구조를 다뤄 봅시다.

7. 휴대폰 자판

5670번

조금 어려운 문제

이번 문제는 사전 내에서 가능한 다음 글자가 하나뿐이라면 그 글자를 버튼 입력 없이 자동으로 입력해 주는 모듈을 사용하면서 단어를 입력하기 위해 버튼을 눌러야 하는 횟수의 평균을 구하는 문제이다.

트라이 클래스를 이용한다. 주어진 단어들을 트라이 구조에 넣은후 찾고자 하는 단어를 입력할때 현재 노드의 자식 노드가 하나밖에 없다면,이는 특정 문자 다음에 오는 문자가 하나밖에 없다는 뜻과 같다는 점 등을 고려하여 구현한다.

Java / Python

• Java

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        String str;

        while ((str = br.readLine()) != null) {
            int N = Integer.valueOf(str);
            List<String> list = new ArrayList<String>();
            Trie trie = new Trie();
            double answer = 0;

            for (int i = 0; i < N; i++) {
                String word = br.readLine(); // 입력 받기
                list.add(word);
                trie.insert(word);
            }

            for (String l : list) {
                answer += trie.contains(l);
            }

            // 평균 출력
            sb.append(String.format("%.2f", answer / N)).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    static class Trie {
        public TrieNode root;

        Trie() {
            this.root = new TrieNode();
        }

        public void insert(String word) {
            TrieNode tempNode = this.root;

            for (int i = 0; i < word.length(); i++) {
                tempNode = tempNode.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode());
            }

            tempNode.setLastChar(true);
        }

        public int contains(String word) { // 존재 여부
            TrieNode tempNode = this.root;
            int cnt = 1;

            tempNode = tempNode.getChildNodes().get(word.charAt(0));

            for (int i = 1; i < word.length(); i++) {
                if (tempNode.getChildNodes().size() >= 2) {
                    cnt++;
                }

                else if (tempNode.getChildNodes().size() == 1 && tempNode.isLastChar()) {
                    cnt++;
                }

                char ch = word.charAt(i);
                TrieNode node = tempNode.getChildNodes().get(ch);

                tempNode = node;
            }

            return cnt;
        }
    }

    static class TrieNode {
        private Map<Character, TrieNode> childNode = new HashMap<>();
        private boolean isLastChar;

        public boolean isLastChar() { // 마지막 문자 확인
            return this.isLastChar;
        }

        public void setLastChar(boolean isLastChar) {
            this.isLastChar = isLastChar;
        }

        public Map<Character, TrieNode> getChildNodes() {
            return this.childNode;
        }
    }
}

• Python

import sys

class Node:
    def __init__(self,chr):
        self.chr = chr
        self.child = {}
        self.check = False

class Trie:
    def __init__(self):
        self.root = Node('')

    def insert(self, word):
        node = self.root
        for w in word:
            if w not in node.child:
                new = Node(w)
                node.child[w] = new
                node = new
            else:
                node = node.child[w]
        node.check = True

    def contains(self, word):
        cnt = 0
        cur = self.root
        for w in word:
            cur = cur.child[w]
            if len(cur.child) > 1 or cur.check:
                cnt+=1
        return cnt

while 1:
    t = Trie()
    words = []
    try: N = int(sys.stdin.readline())
    except: break

    for _ in range(N):
        s = sys.stdin.readline().rstrip()
        t.insert(s)
        words.append(s)
    result = 0
    for word in words:
        result += t.contains(word)

    print("%.2f" % (result/N))

algorithm practice

- 단계별 문제풀기

34. 문자열 알고리즘 1

KMP 알고리즘과 트라이 자료구조를 다뤄 봅시다.

6. 문자열 집합

14425번

트라이보다 쉽게 풀 수 있는 문제지만, 연습을 위해 트라이로 풀어 봅시다.

이번 문제는 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 문제이다.

Java / Python

• Java

트라이를 이용한다. (HashMap을 이용하면 더 빠르고 간단하게 구할 수 있다.)

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

public class Main {
    public static class Node {
        Node[] child = new Node[26];
        boolean is_last;

        public Node() {
        };
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        Node root = new Node();

        while (N-- > 0) {
            String str = br.readLine();
            Node cur = root;
            for (int i = 0; i < str.length(); i++) {
                char cha = str.charAt(i);
                if (cur.child[cha - 'a'] == null)
                    cur.child[cha - 'a'] = new Node();
                cur = cur.child[cha - 'a'];

                if (i == str.length() - 1)
                    cur.is_last = true;
            }
        }

        int answer = 0;
        while (M-- > 0) {
            String str = br.readLine();
            Node cur = root;
            for (int i = 0; i < str.length(); i++) {
                char cha = str.charAt(i);
                if (cur.child[cha - 'a'] == null)
                    break;
                cur = cur.child[cha - 'a'];

                if (i == str.length() - 1 && cur.is_last)
                    answer++;
            }
        }

        bw.write(answer + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

• Python

python으로 트라이를 이용하면 시간 초과가 나 Pypy3로 돌려야 해, python은 그냥 map을 이용하여 간단히 구해보았다.

import sys

N, M = map(int, sys.stdin.readline().strip().split())
str = sys.stdin.read().split()
S, cmd = set(str[:N]), str[N:]
print(sum(1 for i in cmd if i in S))