BOJ 16143 선형대수와 응용

HOLICS 18 문제로 출제된 문제다. 진짜 선형대수 문제인 줄 알고 처박아놨다가 쉬운 문제인 걸 알았다...

문제 링크

---

스포방지선

썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.

---

Solution : \(O(N^2)\)

주어지는 행렬 \(A\)를 어떤 방향그래프의 인접행렬로 해석하자. \(A_{ij} = 0\)이면 에지가 없고, \(A_{ij} > 0\)이면 에지가 있다.

그럼 주어진 문제는 이 가중치 없는 그래프의 지름을 찾는 문제로 바뀐다는 것을 알 수 있다. 그냥 모든 \(i\)에 대해 \(i\)가 시작 정점일 때 \(dist[i \to j]\)를 다 찾으면 된다. 에지 개수가 \(M\)일 때 \(O(MN)\)인데, \(M \le 5N\)이기 때문에 \(O(N^2)\)이 된다.

한 가지 주의할 점은, 악마같은 출제자가 \(A_{ii} > 0\)을 안 써놨다는 거다. (...) 그래서 사실 구해야 하는 게 정확히 지름은 아니고, \(dist[i \to i]\)까지 고려한 답을 내야 한다. 

\(dist[i \to i]\)를 고려하는 방법은 여러 가지가 있다.

내가 쓴 방법은 모든 dist[i][j]를 2차원 배열에 박아놓고 dist[i][j] + dist[j][i]의 min을 구하는 방법인데, i와 인접한 모든 정점을 거리 1로 넣고 multi-source BFS를 돌리는 방법도 있다.