![]()
문제 링크 https://www.acmicpc.net/problem/1867 문제 요약 \(N*N\)격자판위에 돌맹이들이 놓여져 있다. 한번의 작업으로 한개의 행이나 한개의 열에 있는 돌멩이를 모두 제거할 수 있다. 이 때 최소 몇번의 작업을 해야 격자판 위에 있는 돌멩이를 모두 제거할 수 있는지 구하는 문제다. 문제 풀이 처음 이 문제를 본다면 \(greedy\)로 접근을 하기 쉽다. 하지만 그렇게 접근을 시작하는 순간 문제는 미궁으로 빠지게 된다. 그렇다면 어떻게 접근을 해야할까? 우선 아래와 같은 격자판이 있다고 가정을 해보자. 위 격자판을 그래프로 생각해보자. 정점은 각각의 열과 행이고 돌멩이가 있는 칸은 열과 행을 잇는 간선이라고 생각을 한다. 그렇다면 그래프는 아래와 같이 그려진다. 만약에 \..
문제 링크 https://www.acmicpc.net/problem/2843 문제 요약 \(N\)개의 정점가 \(N\)개의 간선을 가지는 방향그래프가 주어진다. 각각의 정점은 최대 한개의 나가는 간선을 가질 수 있다. 이 때 두 가지의 쿼리를 처리해야 한다. 첫 번재 쿼리는 \(x\)번 정점에서 나가는 간선을 지우는 것이도 두 번째 쿼리는 \(x\)번 정점에서 나가는 간선을 따라 계속해서 움직일 때 마지막으로 도착하는 정점이 어디인지, 만약 영원히 끝나지 않는다면 영원히 끝나지 않는다고 출력을 해야 한다. 문제 풀이 연결된 그래프에서 간선을 지워서 두개의 분리된 그래프로 만드는 작업은 생각보다 어려운 일이다. 하지만 반대로 두개의 분리된 그래프를 하나로 합쳐 새로운 그래프를 만드는 작업은 꽤 쉬운 일이다..
방향 그래프가 주어졌을 때 종종 이 그래프 내에서 \(Cycle\)의 존재 유무를 확인해야 할 때가 있다. 이 글에서는 방향 그래프 내에서 싸이클의 존재 유무를 알아내는 알고리즘을 소개하려 한다.기본적인 알고리즘\(Cycle\)의 정의를 한번 생각해 보자. \(Cycle\)이란 정점 \(u\)에서 시작해 어떠한 경로를 지나 다시 \(u\)로 돌아오는 경로가 있다면 이를 \(Cycle\)이라고 한다. 그리고 그래프 내에 이러한 \(Cycle\)이 한개라도 있다면 \(Cycle\)이 존재하는 그래프가 된다. 그렇다면 특정한 시작 정점 \(u\)를 잡고 \(dfs\)를 실행해 다시 시작정점 \(u\)로 돌아오는 경로가 있는지 확인하는 알고리즘을 만든 뒤 모든 정점에 대해 해당 알고리즘을 실행하면 \(Cycle..
