11403번: 경로 찾기

문제 풀이 아이디어

기본적으로 dfs를 통해서 출발점에서 방문할 수 있는 모든 node를 찾아주면 됩니다.

주의!

이 문제는 dfs를 재귀함수로 구현할 때 아래처럼 방문체크를 하고 재귀 함수를 구현하고 다시 방문체크를 취소하는 경우에는 “🚫 시간초과"가 나게 됩니다.

visited[i] = true
dfs(start, i)
visited[i] = false

이 문제는 출발점을 기준으로 다른 node에 갈 수 있는지 알아내는 것이 핵심입니다. 따라서 dfs에 인자로 출발점 (start)를 전달해야 하고요. 같은 맥락에서 dfs를 실행할 때 알고 싶은 것은 start에서 다른 node에 갈 수 있는가이지 start가 아닌 다른 node에서 또 다른 node로 갈 수 있는지는 중요하지 않습니다.

따라서 일단 start에서 해당 node를 방문했다면 방문체크를 취소하지 않고 그냥 두어서 필요없는 추가적인 탐색을 하지 않도록 합시다. 대신 dfs를 실행할 때마다 visited 배열을 리셋해주는 작업을 추가해야 합니다.

코드

// 입력 받기
let N = Int(readLine()!)!
var matrix = [[String]]()
for _ in 0..<N {
    matrix.append(readLine()!.split(separator: " ").map { String($0) })
}

// 정답을 저장하는 배열
var check = Array(repeating: Array(repeating: "0", count: N), count: N)

// dfs를 위한 방문 배열
var visited = Array(repeating: false, count: N)

// dfs 구현
    //⭐️ start를 parameter로 받아야 하는 이유는 check에 시작점을 기준으로 표시해야 하기 때문에
func dfs(_ start: Int, _ now: Int) {
    for i in 0..<N {
        // 길이 있고 아직 방문 안했으면
        if matrix[now][i] == "1" && !visited[i] {
            check[start][i] = "1" //👉 정답 체크하고
            visited[i] = true //👉 방문 체크
            dfs(start, i)
            //⭐️ visited[i] = false 안해줘도 되는 이유
                // 어차피 모든 start에서부터 방문하는 접점을 찾을 것이므로
                // 방문을 초기화해서 다른 start가 아닌 다른 접점에서 i를 방문할 수 있는지 여부를 알 필요가 없다.
        }
    }
}

// 모든 점에서 접점에서 dfs 실행
for i in 0..<N {
    dfs(i, i)
    visited = Array(repeating: false, count: N) //👉 visited는 리셋해주기
}

// 정답 출력
for line in check {
    print(line.joined(separator: " "))
}