어흥

문제 링크: https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 � www.acmicpc.net 1. 주의할 점 - 높이를 1~100까지 모두 시험해보지 말고 가장 낮은 건물높이~가장 높은 건물 높이로 시험한다 2. 구현 - 가장 낮은 건물높이, 가장 높은 건물 높이를 구해서 For문을 반복한다 - 높이 설정을 다르게 할 때 마다 Check[][]배열을 초기화 해준다 - BFS를 통해 잠기는 높이보다 건물이 높으면 Queue에 넣는 방식으로 하며 Cnt를 Result와 비교하며 Re..

문제 링크: https://www.acmicpc.net/problem/6497 6497번: 전력난 문제 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈�� www.acmicpc.net 1. 주의할 점 - 모든 간선의 총합 - MST를 연결할때 드는 최소 비용을 출력한다 - 매 TC마다 Par[] 배열을 초기화 한다 2. 구현 - 크루스칼 알고리즘을 통해 MST를 구현한다 - 입력받는 모든 간선에 대한 정보를 우선순위 큐에 삽입하고, 간선의 가중치가 오름차순이 되도록 정렬한다 - Find_parent(int x) 함수를 통해 X의 부모를 반환한다 - Make_union(in..

문제 링크: https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 1. 주의할 점 - MST 알고리즘에 대해 알고 있어야 한다(필자는 크루스칼 알고리즘을 통해 풀 예정이다) 2. 구현 - 크루스칼 알고리즘을 통해 해당 문제를 해결한다 - Find_parent(int x) 함수를 통해 X의 부모를 반환한다 - Make_union(int a, int b) 함수를 통해 A와 B의 부모가 일치하지 않는다면, 부모의 수가 작은쪽으로 합친다 - 입력받은 간선의 정보를 모두 우선순위큐에 넣고 간선의 크기가 작은것부터 뽑아서 사용한다 - Cycle이 생..

문제 링크: https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이�� www.acmicpc.net 1. 주의할 점 - 위상정렬을 사용할 줄 알아야 한다 2. 구현 - 선행되는 A의 Node에 후행되는 Node B를 추가한다. 그리고 Conn[B]++를 통해 B의 앞에 선행되는 Node가 증가되었음을 표시한다 - For문을 통해 Node 1~N까지 돌며 Conn[]의 값이 0이면 큐에 넣는다 - 큐에서 원소를 뽑으면서 해당 원소를 출력하고, 해당 ..

문제 링크: https://www.acmicpc.net/problem/10473 10473번: 인간 대포 문제 당신은 세계적인 인간대포 서커스 공연자이다. 즉, 당신은 거대한 가짜 대포 안으로 기어올라가 먼 거리를 발사되며 사람들에게 기쁨을 주는 사람인 것이다. 오늘, 당신은 혼자가 아니다. � www.acmicpc.net 1. 주의할 점 - 시작점에서는 대포가 없으므로 무조건 걸어가야 한다 - 다익스트라 알고리즘을 사용한다 2. 구현 - Cal() 함수를 통해 두 점 사이의 빗변의 길이를 반환한다(Hypot 내장함수를 처음알게 되었다) - Arr[][]배열을 통해 대포와 시작 및 도착점의 좌표를 저장한다 - 우선순위 큐를 이용한 다익스트라 알고리즘를 통해 대포를 이용하는 것이 빠른지, 걸어가는 것이 빠..

문제 링크: https://www.acmicpc.net/problem/1719 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net 1. 주의할 점 - 다익스트라 알고리즘을 이용하면서 어떤 방식으로 경로표를 저장할 것인지 고려한다 2. 구현 - 모든 간선들의 정보를 V[] 벡터에 저장한다 - 1~Node까지 모든 Node를 시작점으로 하여 다익스트라 알고리즘을 수행하면서 경로표를 구할 수 있도록 한다 - 시작점에서 출발하는 겨우 tmp.start를 다음 Node로 설정하고, 이외의 경우에는 tmp.start를..

문제 링크: https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다� www.acmicpc.net 1. 주의할 점 - M의 개수가 주어져 있지 않다 - 정답의 개수는 항상 N-1개다. 즉, Dist[a]+ a->G = Dist[b]+b->G의 값이 같다면, MST를 이루는 간선들로 구하자 2. 구현 - 다익스트라를 통해 Node 1번에서 다른 Node들까지의 최단거리를 구하여 Dist[] 배열에 저장한다 - 최단거리를 이루는 간선을 구할때, 1번 Nod..

문제 링크: https://www.acmicpc.net/problem/10282 10282번: 해킹 문제 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염�� www.acmicpc.net 1. 주의할 점 - 단방향 그래프다 - 다익스트라 알고리즘을 사용하면 되며, 매 TC마다 V[] 벡터와,Dist[] 배열을 초기화 해줘야 한다 2. 구현 - 입력받는 그래프의 정보를 V[]에 모두 저장한다 - 시작점을 기준으로 우선순위큐를 사용하여 다익스트라 알고리즘을 통해 각 Node까지의 최단거리를 구한다 - 1~Node의 수 만큼 확인하면서 Dist[]값이 Max가 아니면 Cn..