%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Programming/Coding Assignment
% LaTeX Template
%
% This template has been downloaded from:
% http://www.latextemplates.com
%
% Original author:
% Ted Pavlic (http://www.tedpavlic.com)
%
% Note:
% The \lipsum[#] commands throughout this template generate dummy text
% to fill the template out. These commands should all be removed when 
% writing assignment content.
%
% This template uses a Perl script as an example snippet of code, most other
% languages are also usable. Configure them in the "CODE INCLUSION 
% CONFIGURATION" section.r
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------

\documentclass{article}
\usepackage[hangul]{kotex}
\usepackage{fancyhdr} % Required for custom headers
\usepackage{lastpage} % Required to determine the last page for the footer
\usepackage{extramarks} % Required for headers and footers
\usepackage[usenames,dvipsnames]{color} % Required for custom colors
\usepackage{graphicx} % Required to insert images
\usepackage{listings} % Required for insertion of code
\usepackage{courier} % Required for the courier font
\usepackage{lipsum} % Used for inserting dummy 'Lorem ipsum' text into the template
\usepackage{amsthm,amsmath}

\usepackage{algorithm, algpseudocode}
\usepackage{verbatim} % for commment, verbatim environment
\usepackage{spverbatim} % automatic linebreak verbatim environment
\usepackage{listings}
\usepackage{ulem}
\usepackage{hyperref}
\DeclareGraphicsExtensions{.pdf,.png,.jpg}

\usepackage{xcolor}




% Margins
\topmargin=-0.45in
\evensidemargin=0in
\oddsidemargin=0in
\textwidth=6.5in
\textheight=9.0in
\headsep=0.25in

\linespread{1.25} % Line spacing

% Set up the header and footer
\pagestyle{fancy}
\lhead{구재현 (koosaga)}
\chead{Coder's High 2016} % Top center head
\rhead{2017년 5월 7일 일요일} % Top right header
\lfoot{\lastxmark} % Bottom left footer
\cfoot{} % Bottom center footer
\renewcommand\headrulewidth{0.4pt} % Size of the header rule
\renewcommand\footrulewidth{0.4pt} % Size of the footer rule
\newcommand{\myul}[2][black]{\setulcolor{#1}\ul{#2}\setulcolor{black}}

\setlength\parindent{0pt} % Removes all indentation from paragraphs

%----------------------------------------------------------------------------------------
%	CODE INCLUSION CONFIGURATION
%----------------------------------------------------------------------------------------


\setcounter{secnumdepth}{0} % Removes default section numbers
\newcounter{homeworkProblemCounter} % Creates a counter to keep track of the number of problems



%----------------------------------------------------------------------------------------
%	TITLE PAGE
%----------------------------------------------------------------------------------------

%----------------------------------------------------------------------------------------


\begin{document}

\section{문제 H. Checkpoint : 풀이}
\subsection{요약한 문제 설명}
무방향 그래프가 있고, 도둑이 시작하는 점들의 집합 $S$와 도둑이 끝나는 점들의 집합 $E$가 주어집니다. $S$와 $E$는 교집합이 없습니다. 어떠한 점 $v$를 그래프에서 지웠을 때, $S$에 속하는 임의의 점에서 시작해서 $E$에 속하는 임의의 점에 도달 할 수 없다면, $v$는 "검문소 후보"입니다. 그래프의 모든 검문소 후보를 찾아주세요.

\subsection{문제를 단순화하자}
시작하는 점들과 끝나는 점들이 모두 1개 이상일 수 있습니다. 복잡합니다. 하지만 간단한 아이디어로 이 점들을 정확히 하나로 줄일 수 있습니다. \newline

아이디어는 시작하는 정점과 끝나는 정점들을 묶어주는 슈퍼 노드를 하나 만들어 주는 것입니다. 0번 정점과 $n+1$번 정점을 만듭시다. 그리고, $S$에 속하는 모든 정점들에 대해서 0번 정점과 연결되는 간선을, $E$에 속하는 모든 정점들에 대해서 $n+1$번 정점과 연결되는 간선을 만들어 줍시다. 이제 검문소 후보의 정의는 \newline

\textbf{어떠한 정점 $v$를 그래프에서 지웠을 때, 0번 정점에서 $n+1$번 정점에 도달할 수 없다면, $v$는 검문소 후보이다.} \newline

와 같이 간소화 됩니다. 물론 0번 정점과 $n+1$번 정점은 세면 안 되겠지만요. \newline

이는 문제를 단순화 할 뿐만 아니라, \textbf{절점}을 구하는 문제로 모델링 할 수 있는 가능성도 만들어 줍니다. 해당 점을 지웠을 때, 연결성이 바뀌지 않는다면, 당연히 0번 정점에서 $n+1$ 번 정점까지도 문제 없이 도달할 수 있을 것입니다. 고로, 해당 점을 지우는 것은 그래프의 연결성을 바꿔놓아야 하며, 이는 검문소 후보들은 새 그래프의 절점 중 하나여야 한다는 것을 시사합니다. 

\subsection{절점 개념을 통한 문제 해결}
그래프의 절점을 제거하게 되면, 남은 정점들은 2개 이상의 다른 컴포넌트로 갈라지게 됩니다. 절점이 검문소 후보가 되기 위해서는, 0번 정점과 $n+1$번 정점이 이 과정에서 다른 컴포넌트로 갈라져야 합니다. 이는 절점을 찾는 깊이 우선 탐색(DFS)을 조금 변형시켜 해결할 수 있습니다.\newline

0번 정점을 루트로 잡고 DFS를 합시다. DFS 과정에서, 각각의 정점의 DFS 서브트리에 $n+1$번 정점이 있는지 없는지를 불리언 변수로 가지고 다닙니다. 해당 정점이 절점인 경우를 생각해봅시다. DFS 트리의 서브트리 중에서, 어떠한 서브트리들은 해당 정점을 지워도 0번 정점과 연결되어 있을 것이며, 어떠한 서브트리들은 해당 정점을 지우면 0번 정점과의 연결이 끊깁니다. \newline

이를 판별하기 위해서는, 절점을 판별하는 경우와 똑같은 방법으로 low link를 응용하면 됩니다. 해당 서브트리의 low link가 현재 정점의 방문 시간보다 작다면, 정점을 끊는 것은 $n+1$번 정점과 루트와의 연결에 아무 상관이 없습니다. 하지만 그렇지 않다면, 정점을 끊었을 때 해당 서브트리는 다른 컴포넌트로 갈라지게 됩니다. 만약에 그 서브트리에 $n+1$번 정점이 있다면, 그 절점은 검문소 후보입니다. 고로, 이러한 정점을 단순히 체크해 두면 문제를 해결할 수 있습니다.\newline

일반적인 절점 문제를 해결할 때는 루트에 대한 예외 처리가 필요하지만, 이 문제는 0번 정점이 답이 될 수 없기 때문에 필요가 없습니다. 

\subsection{다른 풀이}
사실 절점 대신 Minimum Cut 문제로 모델링을 해도, Dinic's Algorithm을 사용하면 $O((N+M)^{3/2})$ 정도의 시간 복잡도로 문제를 해결할 수 있습니다. 관련 자료에 대해서는 모든 가중치가 1인 단위 그래프에서 Dinic's Algorithm의 시간 복잡도를 분석한 제 글을 참고하세요. \url{http://koosaga.com/133} \newline

다만 의도된 풀이가 아니라 시간 안에 안 나와도 책임은 못 집니다. 그리고 정해보다 더 어려운 것 같습니다...

\newpage
\end{document}