기록방

👉 문제링크 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 🔸 문제 분석 🔸 N개의 도시 중 M개의 도시를 여행하고자 한다. 경로가 있어서 여행이 가능하면 YES, 불가능하면 NO를 출력한다. 🔸 문제 풀이 🔸 여행 하고자 하는 M개의 도시 간에 경로가 있는지 파악하는 쉬운 방법은 같은 집합에 있는지 확인하는 것이다. 분리 집합(Disjoint Set)으로 N개의 도시들의 집합을 나눈다. 여행 계획상의 도시들이 같은 집합에 있으면 경로가 존재한다는 뜻이다. 분리 집합이 아니라 BFS나 DFS로 Brute F..

👉 문제링크 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 🔸 문제 분석 🔸 무방향 그래프가 주어지면, 이분 그래프인지 아닌지 판별한다. 🔸 문제 풀이 🔸 그래프 탐색을 통해 각 노드가 서로 다른 집합에 속하는지 구분한다. DFS로 처음 방문한 노드에 한번은 A집합, 한번은 B집합으로 번갈아 가며 포함시킨다. 이미 방문한 노드인데, 같은 집합이면 이분 그래프가 아니다. 여러 개의 부분 그래프로 이루어 져있을 수 있으므로, 모든 노드에서 DFS를 시작해본다. 모든 탐색 이후 이분 그래프 판정 결과를 출력한다...

👉 문제링크 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 🔸 문제 분석 🔸 N개의 도시와 도시 사이를 연결하는 M개의 단방향 도로가 존재한다. 도로 하나 당 1의 거리를 갖는다. X번 도시에서 시작해 최단거리가 정확히 X 거리만큼 떨어진 도시의 목록을 출력한다. 🔸 문제 풀이 🔸 하나의 노드에서 다른 모든 노드들의 최단 거리를 구해야 하므로 다익스트라 알고리즘을 사용한다. N은30만개인데, 우선순위 큐를 활용해 O(NlogN)으로 해결..

👉 문제링크 1033번: 칵테일 august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다. 경근이는 인터넷 검색을 통해서 재료 쌍 N www.acmicpc.net 🔸 문제 분석 🔸 10 이하의 자연수 N이 주어지고, N-1 개의 재료 비율이 주어진다. 칵테일을 만드는데 필요한 각 재료의 최소 질량을 출력한다. 🔸 문제 풀이 🔸 기준값을 찾기 위해 입력된 p, q 비율들의 최소공배수를 구한다. N개의 재료와 N-1의 연결 정보는 N개의 노드와 N-1의 간선 정보이므로 트리 형태로 나타낼 수 있다. 한 노드에 값을 넣고 DFS로 인접한 노드를 탐색하며 입력된 비율로 각 노드의 질량 값을 만들어 간다. 모든 노드의..

👉 문제링크 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 🔸 문제 분석 🔸 N x M 모눈종이에 공기와 치즈가 0, 1 로 주어진다. 외부 공기와 2개 이상 맞닿은 치즈는 녹는다. 치즈가 모두 녹는데 걸리는 시간을 구한다. 🔸 문제 풀이 🔸 치즈 내부의 공기와 외부 공기를 분리해서 생각한다. 가장자리 면은 치즈를 두지 않는다고 문제에서 제한했으므로, (0,0)부터 그래프 탐색으로 인접한 0을 2로 바꾼다. 풀이에선 DFS를 사용했다. 공기와 맞닿은 치즈를 녹여 없앤다. 치즈가 녹은 자리는 공기..