플로이드10

• 

  [백준/BOJ] 1058번: 친구 문제 https://www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 해설 2-친구가 되기 위한 조건은 다음과 같다. 서로 친구이다. 한다리 건너 친구이다. 이 문제는 플로이드 와샬 알고리즘을 이용하여 해결하였다. 우선 자기 자신과는 친구를 맺을 수 없으므로 0으로, 나머지는 INF(987654321)로 초기화하였다. 후에 입력으로 Y값이 들어온다면 그 인덱스를 1로 선언하였다. 이제 플로이드 와샬 알고리즘을 수행시켜 몇다리를 건너 아는 사이인지를 모두 구한다. .. PS(Problem Solving)/BOJ 2022. 9. 25.

• 

  [백준/BOJ] 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 해설 bfs로도 풀 수 있겠지만, 나는 이런 문제를 플로이드 와샬 알고리즘을 사용하여 모두 구해놓은 후 그 값들을 통해 해결하는 편을 좋아한다. 배열에서 자기 자신으로 가는 경우의 수는 0으로 초기화해주고, 나머지는 INF(987654321)의 값으로 초기화해주었다. 후에 입력받은 관계 (a, b라 하자)를 1로 저장한다. 즉, arr[a][b.. PS(Problem Solving)/BOJ 2022. 9. 21.

• 

  [백준/BOJ] 13424번: 비밀 모임 문제 https://www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 해설 각 방 사이 비밀 통로를 이용하는 비용이 나와있다. 플로이드 와샬 알고리즘을 이용하여 각 방 사이를 오가는데 필요한 최소 거리를 구해놓은 후, 현재 친구들이 있는 방에서 각 방까지 가장 작은 비용으로 갈 수 있는 방을 찾으면 된다. 코드 import java.util.* import kotlin.collections.ArrayList import kotlin.math.min privat.. PS(Problem Solving)/BOJ 2022. 9. 7.

• 

  [백준/BOJ] 2660번: 회장뽑기 문제 https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 해설 두 회원이 친구 사이라면 1, 친구의 친구 사이라면 2, 친구의 친구의 친구 사이라면 3 ... 과 같이 숫자가 증가한다. 예를 들어 1, 2, 3의 회원이 있을 때, 1번 회원과 2번 회원이 친구 사이이고, 2번 회원과 3번 회원이 친구 사이라면 1번 회원과 3번 회원은 친구의 친구 사이이므로 2의 값을 가지게 된다. 즉, 한 다리를 거쳐 알 수 있다는 것이므로 플로이드 와샬 알고리즘.. PS(Problem Solving)/BOJ 2022. 9. 3.

• 

  [백준/BOJ] 1507번: 궁금한 민호 문제 https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B www.acmicpc.net 해설 플로이드 와샬 알고리즘을 역으로 이용하여 문제를 해결할 수 있다. 플로이드 와샬 알고리즘을 생각해보자. 만약 1번 도로, 2번 도로, 3번 도로가 있을 때, 1 - 2, 2 -3번 간 도로가 있다면 1 - 3번 도로는 없어도 1 - 2 -3을 통해 갈 수 있다. 즉 map[1][3] == map[1][2] + map[2][3]이 되는 것이다. 따라서 이 문제에서는 m.. PS(Problem Solving)/BOJ 2022. 9. 3.

• 

  [백준/BOJ] 1719번: 택배 문제 https://www.acmicpc.net/problem/1719 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net 해설 플로이드 와샬 알고리즘을 응용하여 문제를 해결할 수 있다. 플로이드 와샬을 진행하므로 자기 자신으로 향하는 노드는 0으로, 그 외에는 INF(임의로 지정)으로 초기화해준다. 이후 간선의 정보를 입력받아 어떠한 노드에서 어떠한 노드로 향할 때 얼마의 비용이 드는지를 저장해주고, a->b와 같이 한 번에 갈 수 있는 노드들은 경로를 저장해 줄 배열 path[a][b] = b와 같이 된.. PS(Problem Solving)/BOJ 2022. 9. 1.

• 

  [백준/BOJ] 1613번: 역사 문제 https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 해설 n개의 사건들의 전후 관계가 주어진다. 이를 통해 두 개의 사건의 전후 관계를 알아낼 수 있는지, 안다면 먼저 일어났는지, 후에 일어났는지를 알아내면 된다. 플로이드 와샬 알고리즘을 이용하면 모든 사건들의 전후 관계를 한번의 알고리즘 수행으로 알아낼 수 있다. 전후 관계를 표시할 배열들을 초기값(INF = 987654321이라 하자.)으로 선언해준다. 이때 같은 사건(i == j.. PS(Problem Solving)/BOJ 2022. 8. 30.

• 

  [백준/BOJ] 10159번: 저울 문제 https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 해설 전형적인 플로이드 와샬 알고리즘 문제이다. 플로이드 와샬 알고리즘을 사용하는 문제이므로 우선 물건의 개수만큼의 이중 배열을 선언한다. 나는 이 배열을 boolean 배열로 하였지만, 다른 배열로 하여도 설정만 잘하면 크게 상관없다. 물건 쌍의 개수를 입력받으면, 배열에서의 그 인덱스를 true로 한다. 이는 양방향이 아닌 1 > 2처럼 단방향이므로 한쪽으로만 정.. PS(Problem Solving)/BOJ 2022. 8. 24.

• 

  [백준/BOJ] 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 해설 플로이드 와샬 알고리즘을 사용하여 해결할 수 있는 문제이다. 우선 초기값을 설정할 배열을 map이라 하자. map을 INF(100000000)으로 초기화해주었다. 이후 플로이드 와샬 알고리즘을 수행하여 각 정점에서 각 정점까지의 최단 경로를 구해준다. 플로이드 와샬 알고리즘의 수행이 끝났다면, 사이클을 찾아야 한다. map[i][j]와 map[j][i].. PS(Problem Solving)/BOJ 2022. 8. 9.

• 

  [백준/BOJ] 2458번: 키 순서 문제 https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 해설 플로이드 와샬 알고리즘을 사용해서 문제를 해결하였다. 초기값을 저장할 배열을 BooleanArray로 선언하여 입력으로 알 수 있는 학생들끼리의 관계를 true로 해준다. 이 때 배열[i][j] = true라면, i가 j보다 작다가 되고, 배열[j][i] = true라면, j가 i보다 작다가 된다. 플로이드 와샬 알고리즘을 수행하며, 배열[i][k]와 배열[k][j]가 모두 참일 시, 배.. PS(Problem Solving)/BOJ 2022. 8. 9.