윤만석

문제 때는 2118년…. 세상의 모든 강과 호수가 말랐다..! 하지만 한 곳..! 인경호는 마르지 않았다. 심지어 지하에서 물이 계속 나왔다. 앞으로도 마르지 않을 것 이다. 인하대학교 학생들은 인경호의 물을 식수로 쓰기 위해 정수 시설을 설치 하기로 했다. 정수 시설은 인경호 안에 N개의 구역에 설치 되었다. 정수 시설이 있는 곳에서는 물을 마실 수 있다. 각 구역은 0번부터 N-1번까지 번호를 써놨다. 그리고 정수 시설에는 깨끗한 물만 흐르게 하기 위해 M개의 파이프를 이용해 연결 시켰다. 파이프로 연결된 정수 시설에서 물은 파이프를 통해 한 방향으로만 흐른다. 예를 들어 1번 정수 시설과 2번 정수 시설이 연결 되었다면 1번 정수 시설에서 2번 정수 시설로만 깨끗한 물이 흐르는 것 이다. 또한 2번..

문제 방향 그래프 G = (V, E)가 주어져 있다. 임의의 노드 u, v ∈ V에 대해서 u에서 v로 E에 포함된 간선만을 이용해 갈 수 있는 경로가 있으면 u→v로 표현한다. 만약 어떤 노드 v ∈ V가 자신으로부터 도달할 수 있는 모든 노드로부터 돌아오는 경로가 있다면, 즉 다음 조건을 만족한다면 노드 v ∈ V를 싱크라고 부른다. 조건: ∀w ∈ V, (v→w) ⇒ (w→v) 또한, 그래프 G의 싱크를 모아놓은 집합을 bottom(G)로 표현한다. bottom(G) = {v ∈ V: ∀w ∈ V, (v→w) ⇒ (w→v)} 주어진 그래프 G=(V, E)의 bottom(G)를 구하시오. 입력 입력은 여러 개의 테스트 케이스로 구분되어 있다. 각 테스트 케이스의 첫 줄에는 노드의 수 n (1 ≤ n ..

문제 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자. 이 경우에는 첫째 줄에서 1, 3, 5를 뽑는 것이 답이다. 첫째 줄의 1, 3, 5밑에는 각각 3, 1, 5가 있으며 두 집합은 일치한다. 이때 집합의 크기는 3이다. 만약 첫째 줄에서 1과 3을 뽑으면, 이들 바로..

문제 World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역으로 나누고, 어떤 선수가 A구역에서 B구역으로 이동하게 하는 움직임을 (A, B)로 표현한다. 모든 도현이의 팀 선수들이 이 움직임만을 따라서 이동한다면 승리하리라고 도현이는 확신한다. 도현이는 선수들에게 자신의 전술을 말해주며, 다른 모든 구역에 도달할 수 있는 시작 구역을 찾은 뒤 지시한 움직임만을 따라가라고 했다. 그러나 도현이는 한 가지 간과한 것이 있었는데 그건 선수들이 자신만큼 똑똑하지 않다는 것이다. 선수들은 그러한 시작 구역을 찾는 것이 어려웠다. 이제 당신이 적절한 시작 구역..

문제 평소 일로 바쁘던 태희는 휴가를 통해 여행을 다녀오기로 하였다. 우선 태희는 사전 조사를 통해서 여행하려는 도시를 N(1 ≤ N ≤ 10,000)개 선택하였다. 태희는 비행기를 이용하면 충분히 여행할 수 있을거라 생각했지만, 짐을 꾸리던 중 비행기가 모든 도시들 사이를 다니는 것은 아님을 알게 되었다. 태희는 다시 비행로에 대해 조사를 하였고, 총 M(1 ≤ M ≤ 100,000)개의 비행로가 존재함을 알게 되었다. 각각의 비행로는 한 방향으로의 서비스만을 제공한다. 태희는 S(1 ≤ S ≤ N)번 도시에서 시작해서 T(1 ≤ T ≤ N)번 도시에서 여행을 끝내기로 하였다. 그리고 태희는 도시와 항공로에 대한 정보를 바탕으로 여행 계획을 세우기로 하였다. 도시와 비행로에 대한 정보가 주어졌을 때, ..

문제 인도의 도시 중 하나인 시루세리에는 모든 도로들이 일방통행으로 되어 있다. 도로들이 만나는 모든 교차로에는 시루세리 은행의 현금입출금기(ATM)가 설치되어 있다. 시루세리에는 유명한 레스토랑 체인인 아웃백 커리 하우스가 있다. 이 레스토랑의 각 체인점들은 교차로에만 위치한다. 물론 각 교차로마다 항상 이 레스토랑 체인점이 있는 것은 아니다. 이 레스토랑은 현금만 사용할 수 있다. 시루세리에 사는 반디치는 오늘 오후에 이 레스토랑에서 가족들과 파티를 열려고 한다. 그런데 갖고 있는 현금이 부족하여 레스토랑으로 가는 동안에 가능한 한 많은 현금을 ATM 기기로부터 인출할 계획을 세웠다. 그는 자신의 집에서 출발하여 차로 이동하면서 통과하는 모든 교차로 ATM 기기에 들어있는 현금 전부를 인출하려고 한다..

식 f : (x1||x2)&&(x2||x3)&&(~x1||x3) 와 같이 Or로 연결된 K개의 절로 이루어진 식을 만족하는 해가 존재하는지 묻는 문제입니다. 식 f 의 해는 네이브하게 x1 ,x2 ,x3에 각각 0과 1을 넣으면서 확인이 가능합니다. 하지만 변수의 개수가 많아지면....너무 오래걸립니다. 따라서 다른방법을 고안한게 SCC를 이용한 방법입니다. 하나의 절 x1||x2는 두개의 명제로 나눌 수 있습니다 ~x1->x2 와 ~x2->x1입니다. x1또는 x2둘중에 적어도 하나는 참이여야 하기 때문입니다. 이 명제만을 이용해 함의 그래프를 그릴 수 있습니다. 이 그래프는 대칭을 이룹니다. P->Q 명제를 함의하는 이 그래프는 P가 참일때는 Q는 반드시 참이여야하고 P가 거짓일때는 Q는 참이든 거짓..

문제 방향 그래프가 주어졌을 때, 그 그래프를 SCC들로 나누는 프로그램을 작성하시오. 방향 그래프의 SCC는 우선 정점의 최대 부분집합이며, 그 부분집합에 들어있는 서로 다른 임의의 두 정점 u, v에 대해서 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재하는 경우를 말한다. 예를 들어 위와 같은 그림을 보자. 이 그래프에서 SCC들은 {a, b, e}, {c, d}, {f, g}, {h} 가 있다. 물론 h에서 h로 가는 간선이 없는 경우에도 {h}는 SCC를 이룬다. 입력 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내..