나그네

1507번: 궁금한 민호 문제 https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 풀이 플로이드-워셜 알고리즘을 반대로 거슬러가면 된다. 플로이드-워셜은 i->j 시간보다 i->k , k->j 시간이 더 짧을 경우 i->j를 i->k , k->j로 갱신한다. 이 문제에선 이미 최단 시간이 구해져 있고 도로 개수를 최소화하는 것이 목적이다. 도로를 최소화하기 위해서 필요 없는 도로를 지워야한다. 예를 들면서 차례대로 살펴보자. i->j(직접 연결..

11562번: 백양로 브레이크 문제 https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 풀이 정점 간 양방향, 단방향 간선이 있을 때 출발지에서 목적지까지 경로가 이어지도록 하려면 몇 개의 단방향 간선을 양방향 간선으로 바꾸면 되는지 구하는 문제다. 즉, 최단 경로를 구하되 단방향 간선을 반대로 지나간 횟수를 구하면 된다. 간선은 시작점, 도착점, 방향의 정보를 입력받는다. 예시를 통해 알아보자 임의의 정점 a, b에 대해 a에서 b로 가는 최단..

27512번: 스네이크 문제 https://www.acmicpc.net/problem/27512 27512번: 스네이크 두 정수 $n$과 $m$이 한 줄에 공백으로 분리되어 주어집니다. ($2 \le n,m \le 200$) www.acmicpc.net 풀이 N × M 격자에서 뱀의 머리와 꼬리가 맞닿아 있으면서 길이가 가장 긴 것을 구하는 문제다. 처음엔 사각형 외곽을 두르는 길이라고 생각했으나 사실 꼬불꼬불하게 가면 더 길어질 수 있다. 그리고 규칙이 있는데 N과 M 중 하나라도 짝수면 뱀은 N × M 격자를 모두 지날 수 있다. 둘 중 하나라도 짝수가 아니라면 즉, 둘 다 홀수라면 뱀은 아무리 꼬불꼬불하게 가더라도 한 칸은 지나갈 수 없다. 코드 #include using namespace std;..

27522번: 카트라이더: 드리프트 문제 https://www.acmicpc.net/problem/27522 27522번: 카트라이더: 드리프트 레드팀은 2, 4, 5, 6등을 달성하여 총 $20$점을, 블루팀은 1, 3, 7, 8등을 달성하여 총 $19$점을 기록하였다. www.acmicpc.net 풀이 각 레이서의 기록과 속한 팀을 pair로 받아 배열에 저장한다. 기록은 분:초:밀리초 형태이므로 문자열 오름차순으로 정렬하면 기록이 짧은 순으로 정렬이 된다. 이제 배열을 순회하며 각 레이서의 팀에 등수에 맞는 점수를 더해준다. 점수를 비교해 승리 팀을 출력하면 된다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(false); ..

2458번: 키 순서 문제 https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 풀이 학생들 간 키를 비교해 자신이 몇 번째인지 알 수 있는 학생의 수를 구하는 문제다. 플로이드-워셜 알고리즘을 사용해 주어진 간선은 1, 나머지는 INF로 두고 플로이드-워셜을 돌린다. 정점 u, v의 키를 비교할 때 dist[u][v]가 INF가 아니라면 u보다 v가 키가 큰 것이고 dist[v][u]가 INF가 아니라면 v보다 u가 키가 큰 것이다. 둘 다 아니라면..

13168번: 내일로 여행 문제 https://www.acmicpc.net/problem/13168 13168번: 내일로 여행 첫 번째 줄에는 한국에 있는 도시의 수 N(1 ≤ N ≤ 100)과 1인당 내일로 티켓의 가격 R(1 ≤ R ≤ 1,000,000)이 주어집니다. 두 번째 줄에는 N개의 도시의 이름이 주어집니다. 도시의 이름은 알파벳 대소 www.acmicpc.net 풀이 여러 도시와 도시 간 이동 가능한 교통수단을 입력받고 정해진 순서대로 특정 도시들을 여행하는 최소 비용을 구하는 문제다. 단, 여기서 '내일로'라는 티켓을 구매하면 특정 교통수단은 0원이거나 반값이 된다. 이때 '내일로' 티켓을 구매하는 것이 더 비용이 적게 드는지 구하는 문제다. 특정 도시를 정점으로 사용하기 위해 map을 ..

1956번: 운동 문제 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 풀이 어느 점에서 다른 한 점까지 갔다가 다시 출발점으로 돌아오는 사이클의 길이의 최솟값을 찾는 문제다. 플로이드 워셜 알고리즘으로 각 정점 간 거리를 구하고 모든 경우의 수를 탐색하며 최솟값을 찾는 방식으로 풀었다. 코드 #include using namespace std; #define INF 1e9 int main() { ios::sy..

1613번: 역사 문제 https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 풀이 여러 사건의 선후 관계를 판단하는 문제다. 플로이드-워셜 알고리즘을 사용해 풀 수 있다. a가 b보다 먼저 일어났다고 할 때 dist[a][b] = 1, 나머지는 INF로 플로이드를 돌린다. 그리고 x, y의 선후 관계를 알고 싶을 때, dist[x][y]가 INF가 아니라면 x가 먼저 일어난 일이고(-1 출력), INF면 x가 먼저 일어난 일은 아니다. 이때 ..

1389번: 케빈 베이컨의 6단계 법칙 문제 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 풀이 플로이드-워셜 알고리즘을 사용해 각 사람이 다른 사람에 이르기까지의 단계를 각각 구해 케빈 베이컨의 수를 구하고, 최솟값을 가지는 사람의 번호를 출력하는 문제다. 코드 #include using namespace std; #define INF 1e9 int main() { ios::sync_with_..

11403번: 경로 찾기 문제 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 (i, j)의 값이 0이면 연결되어 있지 않은 것이고 1이면 i->j 연결되어 있는 것이다. 따라서 dist[i][j]에 입력을 받아 0이면 연결되어 있지 않으므로 INF로, 1이면 1을 저장해 준다. 플로이드-워셜 알고리즘으로 모든 최단거리를 구하고 i->j로 갈 수 있는 경우엔 1을, INF라면 0을 출력해 주면 된다. 코드 #include using namespace std; #define INF ..