플로이드 와샬 (4) 썸네일형 리스트형 [프로그래머스] 합승 택시 요금 / 2021 KAKAO BLIND RECRUITMENT - JAVA 🔗 문제 링크 [프로그래머스] 합승 택시 요금 / 2021 KAKAO BLIND RECRUITMENT 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 📝 풀이 과정 모든 정점 간의 거리를 구할 수 있는 플로이드 와샬을 사용했다. 플로.. [백준] 1238번: 파티 - JAVA 🔗 문제 링크 BOJ 1238번: 파티 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 1️⃣ 플로이드-와샬 📝 풀이 과정 학생(i)가 이동하는 경로는 i -> X -> i이다. 따라서 이동하는데 걸리는 시간은 (i -> X) + (X -> i)이므로 학생마다 걸리는 시간을 모두 구할 수 있는 플로이드-와샬 알고리즘이 생각났다. ⏱ 시간 복잡도 플로이드 와샬의 경우 시간복잡도가 O(N3)인데, 학생의 수는 최대 1000이므로 세제곱을 하여도 109 이므로 1초이내에 해.. [백준] 11403번: 경로 찾기 - JAVA 🔗 문제 링크 BOJ 11403번: 경로 찾기 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 📝 풀이 과정 모든 정점에서 다른 정점까지 도달할 수 있는지 탐색할 수 있는지를 판별하는 문제이다. 따라서, 플로이드 와샬 알고리즘을 생각해 볼 수 있는데, 문제에서 N의 범위가 100이하으므로 O(N3)인 플로이드 와샬을 써도 괜찮은 문제이다. k, i, j를 3중 반복문을 통해 탐색하며, 만약 i -> k로 갈 수 있고 k -> j로도 갈 수 있다면, i -> j로 가는 경우가 가능하기 때문에 true로 값을 변경해준다. 💻 코드 import java.. [백준] 9205번: 맥주 마시면서 걸어가기 - JAVA 🔗 문제 링크 BOJ 9205번: 맥주 마시면서 걸어가기 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 📝 풀이 과정 집에서 페스티벌까지 가는데 바로 페스티벌까지 갈 수도 있고, 1군데의 편의점을 들릴 수도 있지만 100군데의 편의점 모두를 들릴 수도 있기 때문에 모두 탐색을 해야한다고 생각했다. n이 100이하이고, n3을 해도 100만이기 때문에 플로이드 와샬 알고리즘을 통해 문제를 해결해보기로 했다. for (int i = 0; i 이전 1 다음
