백준 - 경로 찾기 (11403)

let N = Int(readLine()!)!
var distance = [[Int]]()

// 인접행렬 값 저장
for _ in 0..<N {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    distance.append(input)
}

// 플로이드 와샬 알고리즘 실행
for k in 0..<N {
    for i in 0..<N {
        for j in 0..<N {
            if distance[i][k] == 1 && distance[k][j] == 1 {
                distance[i][j] = 1
            }
        }
    }
}

// 정답 출력
var answer = ""

for i in 0..<N {
    for j in 0..<N {
        answer += "\(distance[i][j]) "
    }
    answer += "\n"
}

print(answer)

플로이드 와샬 알고리즘을 응용하는 문제였다.

단, 이 문제에서는 가중치가 없고 경로 존재 여부만 확인하기 때문에 시작 지점 → 경유지로 가는 경로와 경유지 → 끝 지점 으로 가는 경로가 모두 있는지 확인하고, 있으면 distance 값을 1로 설정한다.