https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1. 서론 되게 전형적인 다익스트라 문제인데... 극악의 정답률을 보고 첫 번째로 놀랐고, 수억 번의 시간초과로 두 번 놀랐으나 결국 내가 부족한 사람이란 걸 깨달은 문제... *다익스트라 문제 구별법 최단경로를 구해야 하는데 간선에 가중치가 있고 그 가중치가 자연수일 때 2. 문제 풀이 방향그래프가 입력으로 주어지고 시작점이 주어진다. 그 시작점을 기준으로 ..

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 1. 서론 아주 유명한 문제. 떠올리는 것에서 1차 고비, 구현하는 것에서 2차 고비가 온 문제다. 근데 막 엄청나게 어렵지는 않다!! 2. 문제 풀이 아주 전형적인 그래프 문제이다. 그래프가 주어지고 그걸 두 개의 구역으로 나누어서 그 그래프가 가지고 있는 값의 차가 가장 작은 값을 구하는 문제이다. 만약 나누는 것이 불가하다면 -1을 출력해야 한다. 입력에서 두 그래프가 연결되어 있다는 것을 0,1로 표시하는 것이..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 1. 서론 DFS와 BFS의 완전 기초 문제인데... 범위 설정 잘못해서 계속 삽질했음 ㅠ.ㅠ 2. 문제 풀이 그래프가 주어진다. 그 그래프를 DFS로 탐색했을 때와 BFS로 탐색했을 때의 결과를 출력하는 문제이다. 조건은 탐색 시에 방문할 수 있는 경우가 여러 개인 경우 더 작은 숫자 먼저 탐색하는 것. DFS와 BFS 코드는 블로그를 참조했다!! (스스로 ..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 1. 서론 그래프를 이용해서 푸는 BFS, DFS 문제!! 2. 문제 풀이 한 컴퓨터가 바이러스에 걸리면 그 컴퓨터와 연결된 모든 컴퓨터는 바이러스에 걸린다. 컴퓨터는 1번부터 번호가 차례대로 매겨지며, 1번 컴퓨터가 바이러스에 걸렸을 경우 1번을 제외한 몇 개의 컴퓨터가 감염되는가를 찾는 것이 문제이다. 컴퓨터가 몇 개인지, 연결되어 있는 컴퓨터 쌍의 수가 입력으로 주어지며 그 뒤로 연결된 컴퓨터 번..