윤만석

문제 때는 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 ..

문제 상근이는 오디션 프로그램 대한민국 아이돌의 예선에 참가중이다. 대한민국 아이돌 오디션 프로그램에서 참가자는 심사위원에게 10분동안 자신의 매력을 발산할 기회를 갖는다. 모든 참가자가 경연이 끝난후에, 심사위원은 모두 모여서 투표를 하게 된다. 각 심사위원은 다음 라운드에 꼭 진출시켰으면 하는 사람(찬성)이나 이번 라운드에서 꼭 탈락시켰으면 하는 사람(반대)을 두 명 고른다. 한 심사위원이 찬성표를 두 개 내는 것과 반대표를 두 개 내는 것도 가능하며, 찬성과 반대를 각각 하나씩 내는 것도 가능하다. 또, 반드시 두 표를 내야 한다. 다음 라운드에 진출하는 참가자의 수는 정해져 있지 않다. 즉, 실력이 참가자의 경연이 모두 나쁜 경우에는 다음 라운드에 진출하는 참가자가 없을 수도 있고, 모두 엄청난 ..

문제 종욱이가 살고있는 나라에는 도시가 N개 있고, 도시의 일부는 일방 통행 도로로 연결되어 있다. 종욱이가 살고있는 나라의 대통령 욱종이는 범죄와 싸우기 위해서 일부 도시에 경찰서를 세우려고 한다. 도시 i에 경찰서를 세우는 비용은 cost[i] 이다. 도시 i에 세운 경찰서가 도시 j를 통제할 수 있으려면, i에서 j로 갔다가, 다시 돌아오는 경로가 존재해야 한다. 도로가 연결되어 있는 상태와 각 도시에 경찰서를 지을 때 필요한 비용이 주어졌을 때, 모든 도시를 통제하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 각 도시에 경찰서를 세우는데 드는 비용이 주어진다. 셋째 줄부터 도로가 연결되어 있는 상태가 한 줄에..

문제 새로운 검색 엔진을 만들었다. 이 검색 엔진은 구글을 뛰어넘는 세계 최고의 검색 엔진이기 때문에, 신뢰도가 높은 결과를 보여줘야 한다. 하지만, 사용자가 검색어를 입력했을 때, 이것에 맞는 결과가 수천, 수만개가 될 수 있으므로, 이 중에 어떤 것이 중요하고, 어떤 사이트를 보여줘야 하는지가 큰 문제이다. 구글은 이러한 것을 사이트를 크롤링해서 자체 알고리즘을 이용해서 사이트의 순위를 매긴다. 우리의 검색 엔진은 다음과 같은 방법을 사용할 것이다. 일단 모든 웹사이트에 1점을 준다. 만약에 웹사이트 A에 웹사이트 B로 가는 링크가 있다면, 웹사이트 B의 점수에 웹사이트 A의 점수를 더한다. 예를 들어, 웹사이트가 총 3개가 있다. A, B, C이다. 일단 모든 웹사이트의 점수는 1이다. 이제, 웹사..

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

문제 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러뜨릴 수 있다. 그러나, 가끔씩 도미노가 다른 블록을 넘어뜨리지 못하게 배치되어 있다면, 우리는 다음 블록을 수동으로 넘어뜨려야 한다. 이제 각 도미노 블록의 배치가 주어졌을 때, 모든 블록을 넘어뜨리기 위해 손으로 넘어뜨려야 하는 블록 개수의 최솟값을 구하자. 입력 첫 번째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 두 정수 N, M이 주어지며 두 수는 100,000을 넘지 않는다. N은 도미노의 개수를, M은 관계의 개수를 나타낸다. 도미노 블록의 번호는 1과 N 사이의 정수다. 다음 ..

2-SAT -3 문제에 이어서 이번엔 식 f를 만족하는 해를 하나 구하는게 문제입니다 위에서는 타잔알고리즘을 이용해 2-SAT문제를 SCC로 묶어서 한 SCC내에 두 정점이 존재하는지 확인을 했습니다. 이때 SCC별로 묶는다면 이 그래프는 사이클이 없는 유향 그래프 , DAG가 됩니다. 따라서 이 사이클이 없는 유향 그래프를 이용하면 해를 하나 정할 수 있게 됩니다. 들어오는 간선이 없는 정점부터 시작해서 간선을 하나씩 지워갈겁니다. 이때 그 정점을 FALSE라고 가정을 하게 되면, 그 이후 접근할 정점은 TRUE든 FALSE든 관계가 없습니다. 반대로 TRUE라고 가정을하면 그 이후 접근할 정점이 FALSE가 되면 안되므로, 모순이 발생할 수 있습니다. 따라서 들어오는 간선이 없는 정점부터 시작해 가능..

문제 방향 그래프가 주어졌을 때, 그 그래프를 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개의 줄에는 간선에 대한 정보를 나타내..