*문제들의 난이도 분류는 종만북 혹은 solved.ac 출처임을 밝힙니다.* ★ 문제는 작성자가 다시 풀어보고 싶은 문제 혹은 어려웠던 문제입니다. +가 붙은 문제는 해당 문제에서 중요하게 생각하는 부분입니다. 일반 DFS 문제 [백준] 텀 프로젝트(9466) - Gold 4 [백준] 빵집(3019) + 그리디 - Gold 2 DFS를 이용하는 알고리즘의 세부 분류들 정말 DFS만을 사용해서 해결하는 간단한 문제들보다는 이를 활용하는 알고리즘을 공부해보자. 위상정렬 문제 모음 [알고스팟] 고대어 사전(DICTIONARY) + DFS 위상 정렬 [백준] 장난감조립(2637) + 다이나믹 - Gold 2 [백준] 최종 순위(3665)★ + 큐 위상 정렬 - Gold 1 [백준] 알고스팟어(2848)★ + 큐..

문제 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)과 비슷한 위상 정렬 문제였다. 처음에는 저번 대회의 순위를 저장하여 등수가 바뀐 쌍에서 저번 대회에 더 순위가 높았던 팀이 이번에는 더 낮은 팀으로 바뀌게 설정하였다.(간선을 이번 대회에서 높은 팀 -> 낮은 팀으로) 이렇게 바뀐 쌍에서만 방향 그래프의 연결을 진행하였더니 아래와 같은 결과가 나왔다. 예제의 입력 저번 대회 ..