문제 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 풀이 최단거리를 구하는 문제인데 출발점이 주어지지 않았습니다. 그렇다면 모든 노드에서 거리를 확인해보아야 하는데 이때 사용할 알고리즘은 플로이드-워셜 알고리즘이 적합해보입니다. 플로이드-워셜 알고리즘 설명 특별하게 이 문제에서는 출발점으로 다시 돌아오는 것까지 계산해야 합니다. 특정 노드까지의 거리를 구한 뒤 다시 출발점으로 돌아오는 경우까지 고려하여 최단 ..
백준/그래프
문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 풀이 한 문제, 한 문제씩 풀어나가는 것을 그래프에 대입하여 노드를 탐색하는 과정으로 생각해봅시다. 조건에 의해 모든 노드를 탐색해야 하고, 먼저 푸는것이 좋은 문제를 반드시 먼저 풀어야 하므로 선행 노드를 반드시 탐색해야 합니다. 따라서 위상정렬로 문제를 해결해야 합니다. 그런데 쉬운 문제(번호가 낮은 노드)부터 해결해야 하므로 현재 풀 수 있는 문제(inde..
문제 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 각 건물마다 선행되어 지어져야할 건물이 존재하기 때문에 위상정렬 문제입니다. 건물마다 들어오는 화살표(indegree)를 저장하고, 자신이 탐색될 때마다 화살표를 하나씩 지우며 화살표의 개수가 0이 될 경우 자신의 건물을 짓고 다음 탐색을 진행합니다. 이때 각 건물들은 독립적으로 지어질 수 있기 때문에 먼저 지어진 건물들을 우선적으로 처리하기 위해 BFS탐색에 우선순위 큐를 활용합..
문제 3584번: 가장 가까운 공통 조상 (acmicpc.net) 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 풀이 두 노드의 공통 조상을 찾는다면 부모 노드로 하나씩 거슬러 올라가며 부모가 같은 노드인지 확인하는 방법이 가장 간단합니다. 우선 부모가 같기 위해서는 루트로부터의 깊이가 같아야 합니다. 그렇기 때문에 주어진 두 노드의 깊이가 다르다면 깊이를 맞춰주는것이 우선입니다. 두 노드의 깊이가 같다면 동시에 하나씩 부모로 거슬러 올라가며 비교를 합니다..
문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 트리에서의 지름은 원과 마찬가지로 내부의 두 점 사이의 거리가 가장 먼 길이를 말합니다. 원에서 가장 먼 두 점은 원 둘레 위의 한 점에서 가장 먼 둘레위의 점입니다. 트리에서도 마찬가지로 적용할 수 있습니다. 리프노드에서 리프노드까지의 거리중 가장 먼 것을 구하면 됩니다. 한 노드에서 가장 먼 (리프)노드를 구하고, 그 노드에서 다시 가장 먼 (리프)노드까지의 거리를 ..
문제 4991번: 로봇 청소기 (acmicpc.net) 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 풀이 위의 문제를 해결하기 위한 여러가지 방법이 있습니다. 우선 각각의 더러운 곳과 로봇의 위치를 노드로하는 그래프를 구하는 것이 좋습니다. bfs 탐색으로 각각의 거리를 간선의 가중치로하는 완전 그래프를 얻을 수 있습니다. 문제에서의 방 크기가 최대 20 x 20이고 최대 노드의 개수는 11개로, 큰 비용없이 그래프를 얻을 수 있습니다. 이제 이 그래프를 활용하여 문제를 해결해봅시다. 방법1 (완전 탐색) 문제에서..
문제 13460번: 구슬 탈출 2 (acmicpc.net) 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 풀이 십자 방향으로 구슬을 움직이며 도착지점까지의 최단거리를 찾는 문제입니다. 최단거리를 찾는 문제이므로 bfs 탐색을 통해 물제를 해결해 보겠습니다. 구현 문제와 살짝 짬뽕되어 문제의 조건도 많고 구현과정도 길어지지만 큰 알고리즘은 bfs 탐색으로 하나씩 정리해나가면 이해할 수 있습니다. 먼저 bfs 탐색 종료 조건부터 알아봅시다. 종료조건 1 - 구슬 ..
문제 11657번: 타임머신 (acmicpc.net) 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이 1번 노드에서 시작해서 각 노드까지의 최단거리를 구하는 문제입니다. 하지만 음의 가중치를 갖는 간선이 있기 때문에 다익스트라 대신 벨만-포드 알고리즘을 활용해야 합니다. 벨만-포드 알고리즘을 이용하여 음수 사이클이 발생하는지 검사한 후 음수 사이클이 발생한다면 -1을 아니라면 각 도시의 최단 경로를 출력해주면 됩니다. 한 가지 주의해야 할 점은 ..
