문제 https://www.acmicpc.net/problem/3977 3977번: 축구 전술 World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 강한 결합 컴포넌트(SCC,Strongly Connected Component)로 해결해야 하는 문제. SCC를 모른다면 굉장히 풀기 힘드니 먼저 공부하고 오자. 방향 그래프에서 두 정점이 서로 이동 가능한 경로가 있는 경우 해당 정점들은 같은 강한 결합 컴포넌트에 속한다. 예를 들어 아래의 방향 그래프에서 같은 SCC끼리를 ..

문제 https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 강결합 컴포넌트(Strongly Connected Component)는 방향 그래프에서만 정의된다. 그래프에서 두 정점에 대해서 양방향으로 이동 가능한 경로가 모두 있을 때 두 정점은 같은 강결합 컴포넌트(SCC)에 속한다. 즉, 그래프의 사이클에서 같은 사이클 내에 존..

절단점/단절점(Articulation point / Cut vertex) 절단점이란 무향 그래프에서 해당 점과 인접한 간선들을 모두 지웠을 때 그래프가 두 개 이상의 컴포넌트(서브 그래프)로 나뉘는 정점을 의미한다. 해설 게시글 [백준] No.11266 - 단절점 (C++, Articulation point) 절단선/단절선 (Bridge / Cut edge) 절단선이란 무향 그래프에서 간선을 지웠을 때 그래프가 두 개 이상의 컴포넌트로 나뉘는 간선을 의미한다. 절단점을 먼저 공부하고 보면 쉽게 풀 수 있다. 해설 게시글 [백준] No.11400 - 단절선 (C++, Bridge)

문제 https://www.acmicpc.net/problem/11400 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 이전 문제에서 단절점/절단점(무향 그래프에서 해당 점과 인접한 간선들을 모두 지웠을 때 그래프가 두 개 이상의 컴포넌트(서브 그래프)로 나뉘는 정점)에 대해서 다루었다. 이번에는 무향 그래프에서 간선을 지웠을 때 그래프가 두 개 이상의 컴포넌트로 나뉘는 간선인 절단선/단절선(Bridge / Cut edge)에 대한..

문제 https://www.acmicpc.net/problem/11266 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 DFS를 응용하여 해결할 수 있는 문제들 중에 하나인 절단점/단절점(Articulation point / Cut vertex)에 대한 문제이다. 절단점(Articulation point / Cut vertex) 절단점이란 무향 그래프에서 해당 점과 인접한 간선들을 모두 지웠을 때 그래프가 두 개 이상의 컴포넌트(서..

문제 www.acmicpc.net/problem/18250 18250번: 철도 여행 한국에는 N개의 도시 C1, C2, ..., CN가 있고, 두 개의 도시를 양방향으로 잇는 M개의 철도 노선이 있다. 철도를 좋아하는 가희는 철도 여행을 하려고 한다. 철도 여행이란 시작 도시에서 도착 도시까 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 오일러 서킷(Eulerian curcit)과 오일러 경로(Eulerian trail)를 알아야 해결 가능한 문제. 분류를 알고 풀어서 풀만 했지만 분류를 모르면 정말 풀기 힘들었을 듯한 문제였다. 일단 오일러 서킷과 경로를 집고 넘어가자. 오일러 서킷(Eulerian curcit) 오일러 서킷은 모든 그래프의 간선을 한 번씩만 순회하여 시..

문제 https://algospot.com/judge/problem/read/WORDCHAIN algospot.com :: WORDCHAIN 단어 제한 끝말잇기 문제 정보 문제 끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이 algospot.com 풀이 종만북 난이도: 하 DFS로 오일러 서킷(Eulerian curcit)과 오일러 경로(Eulerian trail)을 구현하는 문제. 오일러 서킷(Eulerian curcit) 오일러 서킷은 모든 그래프의 간선을 한 번씩만 순회하여 시작 노드로 돌아오는 경로를 의미한다. 오일러 서킷을 만족시키는 그래프는 모든 노드가 짝수의 간선(edge)를 갖는 경우이다..

문제 https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 위상 정렬(Topological Sort)을 이용하여 임계 경로(Critical Path)를 구현하는 문제였다. 임계 경로(Critical Path) 임계 경로는 프로젝트 완성에 필요한 시간을 계산하는 스케줄 관리 도구로 자주 사용된다. 프로젝트는 각각의 작업으로 세분화되고 작업들은 특정 작업이 선수되어야만 하는 의..

문제 www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 [백준] 알고스팟어(2848)과 비슷한 위상 정렬 문제였다. 처음에는 저번 대회의 순위를 저장하여 등수가 바뀐 쌍에서 저번 대회에 더 순위가 높았던 팀이 이번에는 더 낮은 팀으로 바뀌게 설정하였다.(간선을 이번 대회에서 높은 팀 -> 낮은 팀으로) 이렇게 바뀐 쌍에서만 방향 그래프의 연결을 진행하였더니 아래와 같은 결과가 나왔다. 예제의 입력 저번 대회 ..

문제 https://www.acmicpc.net/problem/2637 2637번: 장난감조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 풀이 solved.ac 난이도: Gold 2 위상 정렬(Topological sort)로 해결할 수 있는 문제이다. 다른 위상정렬 문제들과는 조금 다르게 모든 케이스가 DAG가 만족하게 주어지기 때문에 부품수를 계산하는데 집중하면 된다. 이번 문제를 해결하기 위해 큐를 이용한 위상 정렬을 구현하였다. 큐를 이용한 위상 정렬에서는 노드로의 진입 차수(indegree)를..