Baekjoon Online Judge

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='')