-
https://www.acmicpc.net/problem/11403
https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2011403
해당 문제는 가중치 없는 그래프가 주어졌을 때 모든 정점에 대해 갈 수 있는 경로가 있는지 없는지 구하는 문제다.
해당 문제는 예전에 한번 본 적 있었으나 문제를 이해 못 하기도 했고 어떤 식으로 풀어야 할지
감도 안 와서 못 풀다가 이번에 플로이드 와샬을 배운 뒤보니
플로이드 와샬 문제 같아서 플로이드 와샬을 이용해 해결했다.
해당 문제는 조금 다른 점이라면 플로이드 와샬 매트릭스를 만들 때 자기 자신에게 가는 부분에
0이 아닌 최댓값을 주고 문제를 풀어야 한다는 점이다. 이후 부분은 그냥
플로이드 와살을 진행하면 해결 가능하다.
728x90'알고리즘 > Baekjoon' 카테고리의 다른 글
Baekjoon 5525 IOIOI JAVA (0) 2021.11.12 Baekjoon 14503 로봇 청소기 JAVA (0) 2021.11.12 Baekjoon 1389 케빈 베이컨의 6단계 법칙 JAVA (0) 2021.11.12 Baekjoon 11053 가장 긴 증가하는 부분 수열 JAVA (0) 2021.11.12 Baekjoon 12865 평범한 배낭 JAVA (0) 2021.11.12 댓글