-
https://github.com/JUNGSOONIL/JAVA/blob/main/SW%EF%BB%BFAcademy%201263
해당 문제는 인접 행렬이 주어지고 나서
자신을 기준으로 모든 사람을 가는 최솟값을 모두 더한 값이
젤 작은 사람의 값을 반환해 주면 해결 가능한 문제다.
해당 문제는 플로이드 와샬 알고리즘을 이용해서 해결했다.
처음에 배열을 큰 값인 10000000로 Arrays.fill을 이용해 채워준 뒤
입력값을 입력해 주는데 이때 값이 0인 부분은 입력해 주지 않고
i와 j 가 같은 곳 즉 자기 자신으로 가는 곳에는 0을 입력해 준다
이후 3중 반복문을 도는데 k 경우지 i 출발지 j 도착지 순으로 돌면서 값을 비교해
넣어준다.
점화식은 arr[i][j] = Math.min(arr[i][k] + arr[k][j], arr[i][j])와 같고 3가지 조건을
판단해서 값을 넣어줘야 하는데
1. 출발지와 경유지가 같을 경우
2. 도착지와 경유지가 같을 경우
3. 도착지와 출발지가 같을 경우
를 제외하고 값이 들어가도록 하고 이후 저장된 배열을 통해 행끼리 값을 더하고 비교해서
최솟값을 출력해 주면 된다.
728x90'알고리즘 > SW Academy' 카테고리의 다른 글
SW Academy 5604 구간 합 JAVA (0) 2021.11.03 SW Academy 8458 원점으로 집합 JAVA (0) 2021.11.02 SW Academy 3307 최장 증가 부분 수열 JAVA (0) 2021.11.02 SW Academy 2005 파스칼의 삼각형 JAVA (0) 2021.11.02 SW Academy 11315 오목 판정 JAVA (0) 2021.11.02 댓글