문제 https://www.acmicpc.net/problem/11495 11495번: 격자 0 만들기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n과 m (2 ≤ n, m ≤ 50)이 주어지며, n은 격자의 행 개수, m은 격자의 열 개수를 나타낸다. 그 다음 n개의 줄에 각각 www.acmicpc.net 풀이 solved.ac 난이도: Platium 2 그래프 모델링이 필요한 최대 유량 문제. 문제의 설명에서는 연산을 한 번씩 진행하여 각 정수를 1씩 줄이지만 생각해보면 어떤 정수끼리 짝을 짓는 가는 중요하지 않다. 예제의 입력을 생각해보면 어떤 짝이든 짝지은 두 정수를 최대한 줄여주면 결과는 동일하다. 여기서 연산을 한번 진행할 때 전체 값의 합은 2씩 줄어드는..

문제 https://algospot.com/judge/problem/read/MATCHFIX algospot.com :: MATCHFIX 승부조작 문제 정보 문제 한때 세계대회 준우승까지 하며 최강의 프로그래머로 칭송 받았던 J씨는 성적이 떨어진 이후 유혹을 이기지 못하고 승부 조작의 세계에 손을 댔습니다. 프로그래밍 대 algospot.com 풀이 종만북 난이도: 중 이 문제를 최대 유량(네트워크 유량)으로 해결하는 방법은 다음과 같다. 이번 문제에서 유량은 승리의 횟수로 생각해 보자. 1. Source에서 각 결승 경기로의 간선 경기는 단 한 번씩만 진행할 수 있기 때문에 간선의 용량은 1로 설정해주자. 결국 모든 경기는 진행되어야 하므로 source에서 각 경기로는 1의 유량이 흐르게 된다. 2. ..

문제 https://www.acmicpc.net/problem/2316 2316번: 도시 왕복하기 2 N개의 도시가 P개의 양방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 오가며 워해머를 한다. 성실한 이석원은 두 도시 사이를 최대한 많이 왔다 갔다 하려 하는데, 이때 한 번 방 www.acmicpc.net 풀이 solved.ac 난이도: Platium 3 정점 분할 테크닉을 통해 풀어야 하는 최대 유량 문제. 최대 유량에 대해서 잘 모른다면 다음 게시글을 참조하자. [네트워크 유량] Network Flow(최대 유량, 최소 컷) 알고리즘 정점 분할이란 정점에도 간선처럼 가중치를 주기 위해 정점을 하나의 간선으로 만드는 기법이다. 이때 간선을 정점처럼 취급하기 위해 정점을 두개의 정점..

문제 https://www.acmicpc.net/problem/1420 1420번: 학교 가지마! 첫째 줄에 도시의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 100) 둘째 줄부터 N개의 줄에 도시의 모양이 주어진다. 비어있으면 점('.'), 벽은 '#', 도현이의 위치는 K, 학교의 위치는 H이다. www.acmicpc.net 풀이 solved.ac 난이도: Platium 2 최소 컷 (최대 유량)알고리즘에 정점 분할을 적용해야 하는 문제. 정점 분할이란 정점에도 간선처럼 가중치를 주기 위해 정점을 하나의 간선으로 만드는 기법이다. 이때 간선을 정점처럼 취급하기 위해 정점을 두개의 정점(in과 out)으로 분할 한다. in정점은 해당 정점으로 들어오는 간선들과 연결해주고 out정점..

문제 https://www.acmicpc.net/problem/6086 6086번: 최대 유량 첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 이름부터가 최대 유량인 최대 유량 문제. 최대 유량 알고리즘과 이번 풀이의 기본 지식을 알기 위해 다음 게시글을 참고 하자. [네트워크 유량] Network Flow(최대 유량, 최소 컷) 알고리즘 기본적인 최대 유량 알고리즘을 적용하기에는 약간 다른 점이 있는데 파이프는 양방향으로 존재하고 같은 두 정점이 여러 간선으로 이어질..

[네트워크 유량] Network Flow(최대 유량) 그래프에서 두 정점 사이에 얼마나 많은 유량(flow)을 보낼 수 있는지 계산하는 알고리즘을 네트워크 유량(Network Flow) 혹은 최대 유량(Maximum Flow) 알고리즘이라고 합니다. 일단 해당 알고리즘에서 사용하는 용어부터 설명하겠습니다. (네트워크 유량 알고리즘에서 간선은 두 정점을 잇는 파이프라고 생각하면 이해하기 쉽습니다.) 용량(Capacity) c(u, v)는 정점 u에서 v로 가는 간선의 용량(가중치)라고 합니다. 유량(Flow) f(u, v)는 정점 u에서 v로의 간선에 실제로 흐르는 유량을 의미합니다. 잔여 용량(Residual Capacity) 간선의 용량과 유량의 차이를 의미합니다. r(u, v) = c(u, v) - ..

문제 https://www.acmicpc.net/problem/4792 4792번: 레드 블루 스패닝 트리 무방향, 무가중치, 연결 그래프가 주어진다. 그래프의 각 간선은 빨간색 또는 파란색으로 색칠되어져 있다. 이 그래프의 스패닝 트리 중 파란색 간선이 정확히 k개인 것이 있는지 없는지 알아내 www.acmicpc.net 풀이 solved.ac 난이도: Platium 3 최소 스패닝 트리(MST)를 적용하여 해결하는 문제. 처음에는 어떤 부분이 MST 문제인지도 감을 못 잡아서 결국 다른 분의 풀이를 보고 해결했다. 4Legs_Archives님의 [백준]레드 블루 스패닝 트리 풀이 문제의 풀이는 난이도에 비해 간단하지만 증명을 어떻게 유도하는 것이 어려웠다. 일단 풀이는 다음과 같다. 1. 파란 간선의..

*문제들의 난이도 분류는 종만북 혹은 solved.ac 출처임을 밝힙니다.* ★ 문제는 작성자가 다시 풀어보고 싶은 문제 혹은 어려웠던 문제입니다. +가 붙은 문제는 해당 문제에서 중요하게 생각하는 부분입니다. [알고스팟] 근거리 네트워크(LAN) + 프림 - 하 [백준] 복제 로봇(1944) + 크루스칼 - Gold2 [백준] 행성 터널(2887)★ + 크루스칼 - Gold1 [백준] 유럽 여행(1185) + 크루스칼 - Platium 4 [알고스팟] 여행 경로 정하기(TPATH)★ + 크루스칼 - 상 [백준] 레드 블루 스패닝 트리(4792)★ + 사이값 판정 - Platium 3

문제 https://algospot.com/judge/problem/read/TPATH algospot.com :: TPATH 여행 경로 정하기 문제 정보 문제 당신은 철도망을 이용해 한 도시에서 다른 도시까지 여행을 하고 싶다. 철도망은 여러 개의 역들과 그들을 잇는 노선으로 구성되어 있다. 각 구간별로 철도의 algospot.com 풀이 종만북 난이도: 상 최소 스패닝 트리(MST, Minimum Spanning Tree)을 잘 응용해야 풀 수 있는 문제. MST 문제임에도 0번 도시에서 N-1번 도시까지의 경로 중 속도 차이의 최솟값을 묻고 있다. 최단 경로와는 다르게 경로들 중에서 최대 속도와 최소 속도의 차가 최소가 될 수 있게 만드는 길을 찾고 있다. 이런 문제에서 MST를 어떻게 이용해야 할..

문제 https://www.acmicpc.net/problem/1185 1185번: 유럽여행 첫 줄에는 방문할 나라의 수 N(5 ≤ N ≤ 10,000)과 이 나라들 사이를 연결하는 길의 수 P(N-1 ≤ P ≤ 100,000)가 주어진다. 두 번째 줄에는 N+1번째 줄까지 i+1번째 줄에는 i번째 나라를 방문할 때 드는 비 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 간선의 가중치를 알맞게 변경시켜주어야 해결할 수 있는 최소 스패닝 트리(MST) 문제. 일단 문제를 읽어보면 MST 문제임을 알리는 힌트를 준다. N개의 나라가 서로 연결된 것을 유지시키면서 최대한 많은 길을 지도에서 제거하고자 한다. 즉, N-1개의 길만을 남겨야 할 것이다. 하지만 문제의 힌트를 읽어보..