플로이드 워셜

[프로그래머스] 합승 택시 요금 (Java)

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 플로이드 워셜 풀이 예제 그림을 보면 정점이 6개이므로 같이 택시를 탈 수 있는 경우의 수도 다음과 같이 6가지이다. (cost(i, j) = 정점 i에서 정점 j까지 드는 최소 비용) 1번 정점까지 합승 = cost(4, 1) + cost(1, 6) + cost(1, 2) 2번 정점까지 합승 = cost(4, 2) + cost(2, 6) + cost(2, 2) 3번 정점까지 합승 = cost(4, 3) + cost(3, 6) + cost(3, 2) 4번 정점까지 합승 = cost(4, 4) +..

[백준] 11562. 백양로 브레이크 (Java)

문제 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 알고리즘 그래프, 플로이드 워셜 풀이 b가 0이라면 일방통행 길이므로 양방향으로 변경해야 갈 수 있기 때문에 dist[v][u]를 1로 두고, b가 1이라면 양방향이므로 변경하지 않아도 갈 수 있기 때문에 dist[v][u]를 0으로 둔다. 모든 입력에 대해 위의 방식으로 초기화해준 후 플로이드 워셜 알고리즘을 사용하면 정답을 구할 수 있다. 코드 import java.io.BufferedReader; import java.io.IOException; im..

[백준] 1719. 택배 (Java)

문제 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 알고리즘 그래프, 플로이드 워셜 알고리즘 풀이 모든 정점에서 다른 모든 정점으로 가는 최단 경로로 가기 위한 다음 정점을 구하는 문제이다. 따라서 이를 저장할 2차원 배열을 만들고, 입력 값이 들어왔을 때 도착 정점으로 설정해준다. 예를 들어 2 4 5 라는 입력 값이 들어왔다면 현재 2에서 4로 가기 위한 최단 경로의 다음 정점은 목적지인 4 인 것이다. 플로이드 워셜 알고리즘을 진행하면서 기존과 동일하게 i에서 j로 갈때 k를 경유하는게 더 짧은 경로라면 최솟값..

[SWEA] 5643. 키 순서 (Java)

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 알고리즘 그래프, 플로이드 워셜(Floyd Warshall) 알고리즘 풀이 백준의 2458. 키 순서 문제와 동일한 문제로 해당 글과 풀이도 동일하다. 자신의 키가 몇 번째인지 알기 위해서는 자신보다 키가 작은 학생이 몇 명인지, 키가 큰 학생이 몇 명인지 알아야한다. 자신보다 키가 작은 학생은 그래프 상에서 [i][j]로, 자신보다 키가 큰 학생은 그래프 상에서 [j][i]로 표현될 수 있다. 예를 들어 예제 그림에서처럼 5번 학생이 4번 학생보다 키가 작다는 것을 graph[5][4] = true 로 표현한다면 6번 학생이 4번 학생보다 키가 크다 = 4..

[백준] 2458. 키 순서 (Java)

문제 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 알고리즘 그래프, 플로이드 워셜(Floyd Warshall) 알고리즘 풀이 자신의 키가 몇 번째인지 알기 위해서는 자신보다 키가 작은 학생이 몇 명인지, 키가 큰 학생이 몇 명인지 알아야한다. 자신보다 키가 작은 학생은 그래프 상에서 [i][j]로, 자신보다 키가 큰 학생은 그래프 상에서 [j][i]로 표현될 수 있다. 예를 들어 예제 그림에서처럼 5번 학생이 4번 학생보다 키가 작다는 것을 graph[5][4] = true 로 표현한다면 6번 학생이 4번 ..

[SWEA] 1263. 사람 네트워크 2 (Java)

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 알고리즘 그래프, 플로이드 워셜(Floyd Warshall) 풀이 사용자 i의 다른 모든 사용자까지의 최단거리의 합을 CC(i) 라고 할 때, 모든 사용자의 CC 값 중 최솟값을 출력하는 문제이다. 따라서 플로이드 워셜 알고리즘을 이용해 모든 사용자로부터 다른 모든 사용자까지의 최단거리를 구하고 각 사용자마다 다른 모든 사용자까지 가는 최단 거리의 합(CC(i))을 구하고 최솟값을 갱신한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader..

[백준] 2660. 회장뽑기 (Java)

문제 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 알고리즘 플로이드 워셜 풀이 모든 회원과 친구이면 1점, 모든 회원이 친구이거나 친구의 친구이면 2점, 모든 회원이 친구이거나 친구의 친구이거나 친구의 친구의 친구이면 3점 ... 위에 적힌 문제의 조건을 생각해보면 어떤 회원의 점수는 모든 간선의 가중치가 1인 그래프에서 다른 모든 회원까지 가는 최단거리 중 최댓값임을 알 수 있다. 따라서 플로이드 워셜 알고리즘을 통해 모든 회원에서 다른 모든 회원까지 거리를 계산한 후, 다른 모든 회원까지 가는 최단거리..

[백준] 1507. 궁금한 민호 (Java)

문제 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 알고리즘 플로이드 워셜(Floyd Warshall) 풀이 도시 간 최소 이동 시간이 입력으로 주어지기 때문에 플로이드 워셜 알고리즘을 이용해 모든 도시 간 경로를 탐색하며 없어도 되는 도로를 삭제하는 식으로 풀었다. 다음은 입력 1의 예제를 그래프로 표현한 것이다. 1->3 간선이 삭제되었음을 알 수 있다. 1->3 간선을 삭제하는 이유는 1->2 , 2->3 간선의 합과 동일하기 때문에 1->3 을 직접 잇는 도로가 존재하지 않았고, 15라는 시간은 ..

[백준] 23258. 밤편지 (Java)

문제 23258번: 밤편지 $C = 3$일 때, 1번 정점에서 4번 정점으로 가는 경로 중 3번 정점을 지나는 경로는 반딧불이 3번 정점에서 8방울의 이슬을 마시고 잠들어버리기 때문에 불가능하다. 따라서 가능한 경로는 2번 정점 www.acmicpc.net 알고리즘 다이나믹 프로그래밍(DP), 플로이드-워셜 알고리즘(Floyd Warshall) 풀이 Q가 최대 50만으로 V2 보다 훨씬 크기 때문에 다익스트라 알고리즘을 이용하면 시간 초과가 날 것이다. 따라서 V3의 플로이드 워셜 알고리즘으로 모든 경우의 값을 저장하고 이를 출력한다. 만약 C가 3인 반딧불이는 어느 마을까지 이동할 수 있을까 23 = 8 방울을 마실 수 있으므로 3번 마을부터는 이동할 수 없을 것이다. 1번 마을에서 21 = 2 방울,..

[백준] 17182. 우주 탐사선 (Java)

🔒 문제 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 🔑 알고리즘 플로이드 워셜 💡 풀이 모든 정점을 탐사해야하기 때문에 모든 정점에서 다른 모든 정점으로 가는 최소 시간을 알아야한다. 따라서 N이 최대 10이므로 O(N3) 시간 복잡도를 가지는 플로이드 워셜을 사용할 수 있다. 플로이드 워셜로 최소 시간을 계산해놓고, K를 제외한 나머지 행성의 순서를 구해(순열) 시간의 합을 갱신한다. ✏️ 코드 import java.io.BufferedReader; import java.io.IOException;..