https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 문제 설명에 나와있듯이, 이분 그래프란 "그래프의 정점을 두 개의 집합으로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는" 그래프입니다. 이를 만족하기 위해서 그래프의 인접한 두 정점은 서로 다른 집합에 속해야 합니다. 예를 들어, 왼쪽과 같은 그래프가 있습니다. 각 노드는 빨간/파란색인데, 이 색은 집합을 나타냅니다. 왼쪽의 그래프는 사실 오른쪽 그래프로 변환 가능합..
'강한연결요소'라고 불리는 Strongly Connected Component (SCC)에 대해 알아봅시다. 1. SCC의 정의 방향 그래프 $G=(V, E)$에서, 어느 노드들의 그룹 $X$가 있다고 했을 때, $X$에서 임의의 두 노드 $u, v$를 골랐을 때 $u$에서 $v$로 가는 경로가 존재한다라는 조건을 만족시키면 $X$를 strongly connected component라고 합니다. SCC의 정의는 maximal하게 형성된 strongly connected component입니다. maximal하다는 것이 무엇인지 아래의 예시를 통해 알아봅시다. 위와 같은 방향 그래프에서 세 노드로 구성된 초록색 그룹이 SCC입니다. 파란색 노드는 그 자체로서 SCC입니다. 그런데 두 개의 초록색 노드를 ..
이 글은 Problem Solving를 위한 스프라그-그런디 이론 기초 설명입니다. 먼저 님 게임을 알아봅시다. Nim game 돌 무더기 \(n\)개가 있고, 각 돌 무더기는 \(p_{1}, p_{2}, ... ,p_{n}\)개의 돌로 구성되어 있습니다. 두 명의 플레이어는 자신의 차례마다 돌 무더기 하나를 고른 뒤, 그 돌 무더기에서 $1$개 이상의 돌을 덜어냅니다. 자신의 차례에 덜어낼 돌이 없는 플레이어가 패배합니다. 즉, 마지막 돌을 가져간 플레이어가 승리합니다. 님 게임에서 두 플레이어가 완벽하게 플레이했을 때 선공/후공 중 누가 이기는 지는 정해져 있습니다. 두 플레이어 모두 최적으로 행동한다는 전제하에, winning state에서 턴을 가지는 플레이어는 반드시 승리하며, losing st..