나그네

11780번: 플로이드 2 문제 https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 제목부터 노골적으로 플로이드-워셜 알고리즘을 사용하는 문제임을 보여준다. 그리고 각 정점에서 다른 정점으로 갈 때 최단 경로 중 하나를 출력해줘야 하므로 path 배열을 만들어 최단 경로가 갱신될 때마다 i -> k의 경로, k -> j의 경로를 중복되는 k를 제외하고 합쳐준다. 이를 vector의 insert 함수를 사용해서 합쳐서 만들어줬다. 그리고 p..

2660번: 회장뽑기 문제 https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 풀이 어느 회원이 다른 모든 회원과 연결연결되어 있으면서 점수가 가장 작으면 회장 후보가 된다. 회장 후보가 되기 위한 점수와 회장 후보의 수, 그리고 누가 회장 후보인지 구하는 문제다. 각 회원 간 관계를 구해야 하므로 플로이드-워셜 알고리즘을 사용해 가장 친구의 친구의 친구의... 인 관계를 구한다. 각 친구 관계를 입력받아 양방향 간선 형태로 연결해 준다. 각 회원..

2617번: 구슬 찾기 문제 https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 풀이 N개의 구슬들의 무게를 비교한 정보가 M개 있을 때, 이를 가지고 무게가 중간일 수 없는 구슬의 수를 구하는 문제다. 기본적인 개념은 i번 구슬보다 무거운 구슬의 수나 가벼운 구슬의 수가 N/2보다 크면 그 구슬은 중간일 수 없다. 따라서 각 구슬 간의 무게를 모두 비교하기 위해 플로이드-워셜 알고리즘을 사용했다. 무게 관계 a, b는 a가 b보..

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로 가는 최단..

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_..