나그네

1833번: 고속철도 설계하기 문제 https://www.acmicpc.net/problem/1833 1833번: 고속철도 설계하기 첫째 줄에 자연수 N이 주어진다. 다음 N개의 줄에는 인접행렬 형태로 두 도시 사이에 고속철도를 설치할 때 드는 비용이 주어진다. 이 비용은 각각 10,000을 넘지 않는 자연수이다. 만약 비용이 음 www.acmicpc.net 풀이 최소 스패닝 트리(MST) 응용문제다. 주어진 인접 행렬에 따라 (i, j)의 값이 양수이면 간선을 추가하고, 음수라면 이미 연결되어 있는 간선이므로 i와 j를 union 해주고 전체 비용에 비용의 절댓값을 추가해 준다. 그리고 인접 행렬은 같은 값이 2번씩 입력되므로 ÷2를 해주어 미리 연결되어 있는 간선들의 가중치를 구해준다. 이제 크루스칼..

14621번: 나만 안되는 연애 문제 https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 풀이 최소 스패닝 트리(MST) 응용문제로 남초 대학교와 여초 대학교를 연결하는 도로로만 이루어져 있으므로 간선을 입력받을 때 한 학교는 남초, 나머지 학교는 여초이면 된다. 따라서 배열을 만들어 각 학교가 남초인지 여초인지 저장하고 간선을 입력받을 때 조건문만 추가해 주면 된다. 그리고 모든 학교를 연결할 수 없는 경..

1185번: 유럽여행 문제 https://www.acmicpc.net/problem/1185 1185번: 유럽여행 첫 줄에는 방문할 나라의 수 N(5 ≤ N ≤ 10,000)과 이 나라들 사이를 연결하는 길의 수 P(N-1 ≤ P ≤ 100,000)가 주어진다. 두 번째 줄에는 N+1번째 줄까지 i+1번째 줄에는 i번째 나라를 방문할 때 드는 비 www.acmicpc.net 풀이 모든 나라를 방문해야 하고 길은 N-1개만 남겨야 하므로 최소 스패닝 트리(MST) 알고리즘을 사용한다. 보통 최소 스패닝 트리 문제는 간선의 가중치가 이동 거리, 시간, 비용 등인데 이 문제에서는 방문한 나라에 도착한 시점에 내는 비용도 고려해야 한다. 따라서 도착한 지점의 비용을 어떻게 처리할 것인지가 문제를 푸는 핵심이다...

4792번: 레드 블루 스패닝 트리 문제 https://www.acmicpc.net/problem/4792 4792번: 레드 블루 스패닝 트리 무방향, 무가중치, 연결 그래프가 주어진다. 그래프의 각 간선은 빨간색 또는 파란색으로 색칠되어져 있다. 이 그래프의 스패닝 트리 중 파란색 간선이 정확히 k개인 것이 있는지 없는지 알아내 www.acmicpc.net 풀이 파란색 간선의 가중치를 1, 빨간색 간선의 가중치를 0으로 해서 간선을 추가한다. 간선을 가중치를 기준으로 오름차순 정렬하여 파란색 간선의 수를 최소로 한 스패닝 트리의 가중치(파란색 간선의 수)를 minBlue, 내림차순 정렬하여 최대로 한 스패닝 트리의 가중치를 maxBlue로 저장한다. minBlue ≤ K ≤ maxBlue를 만족하면 1..

1368번: 물대기 문제 https://www.acmicpc.net/problem/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 풀이 최소 스패닝 트리(MST) 응용문제로 물을 끌어오는 비용과 우물을 파는 비용을 비교해야 한다. 따라서 가상의 정점을 만들고 i번째 우물을 파는 비용을 가상의 정점과 i번째 정점을 잇는 간선으로 추가해 주면 된다. 그리고 인접 행렬에서 각 정점 간 물을 끌어오는 비용을 간선으로 추가한다. 이제 크루스칼 알고리즘을 사용해 최소 스패닝 트리의..

1774번: 우주신과의 교감 문제 https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 풀이 모든 우주신들 간 최단 통로로 연결이 되어있어야 하므로 최소 스패닝 트리(MST)를 구하면 된다. 모든 우주신의 좌표를 입력받은 후 서로 간의 거리를 모두 구해 간선으로 추가한다. 이후 이미 연결된 통로인 경우에는 미리 두 점을 union 시켜 MST에서 제외시켜 주고 크루스칼 알고리즘을 사용해 MST를 구한다. 이때 구해지는 가중..

9373번: 복도 뚫기 문제 https://www.acmicpc.net/problem/9373 9373번: 복도 뚫기 각 테스트 케이스마다 센서에 감지되지 않고 복도를 지나갈 수 있는 원형 물체의 최대 반지름을 부동소수점 실수로 한 줄에 출력한다. 물체는 매우 정밀하게 움직일 수 있다고 가정한다. 만약 www.acmicpc.net 풀이 센서에 감지되지 않고 복도를 지나가기 위해서는 각 센서의 감지 범위 바깥으로 지나가야 하고 벽을 벗어날 수도 없다. 우리가 구하고자 하는 것은 끝까지 통과할 수 있는 가장 긴 길이이다. 즉, 작은 간격부터 탐색하다가 특정 조건에서 답이 구해지는 것이다. 풀이에 사용된 방법은 최소 스패닝 트리(MST) 알고리즘이다. 크루스칼(Kruskal) 알고리즘을 사용한 방법으로 문제를..

1976번: 여행 가자 문제 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이 인접 행렬을 입력받아 인접한 도시끼리 union 시켜준 다음 여행 계획에 포함되어 있는 도시들이 모두 같은 집합 안에 있는지 즉, find 값이 모두 같은지 확인하면 된다. 코드 #include using namespace std; vector p; int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x];..

1717번: 집합의 표현 문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 풀이 유니온 파인드 구조 연습 문제다. 두 가지 연산이 있는데 집합을 합치는 연산과 두 원소가 같은 집합 안에 있는지 확인하는 연산이 있다. 첫 번째 연산은 당연히 union하는 연산이고 두 번째 연산은 두 원소를 find한 값이 같은지 여부를 확인하는 연산이다. 문제에 주어진 대로 코드를 작성하기만 하면 된다. 코드 #inclu..

2638번: 치즈 문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 공기에 두 면이 접촉해 있는 치즈는 사라진다. 발상이 중요한 문제로 치즈를 기준으로 탐색할지, 공기를 기준으로 탐색할지 기준을 잘 세워야 하는 문제다. 정답 풀이 이 문제에서 같은 시간에 사라지는 치즈가 모두 사라진 뒤 동시에 공기가 침투한다. 따라서 치즈가 사라지는 로직과 공기가 퍼지는 로직이 턴제로 진행되야 한다. 중요! 모눈종이의 맨 가장자리는 치즈가..