조금은 쉽게 생각할 필요가 (#11403 경로찾기)

#11403 경로찾기 https://www.acmicpc.net/problem/11403

 

 

너무 어렵게 생각했다.

bfs를 여러번 돌리면 되는데,

뭔가 한 번의 함수 실행으로 완벽하게 해결하고 싶어서 더 고민을 했다.

 

 

하하하하하하

 

n = int(input())
links = [[int(x) for x in input().split()] for __ in range(n)]

# bfs
answer = [[0 for _ in range(n)] for __ in range(n)]


def bfs(start):
    # print(start)
    q = [start]
    visited = [0 for _ in range(n)]

    while q:
        prev = q.pop(0)
        for i in range(n):
            if links[prev][i] and not visited[i]:
                # print(prev, i)
                answer[start][i] = 1
                visited[i] = 1
                q.append(i)


for i in range(n):
    bfs(i)

for v in answer:
    print(*v)

 

 

이 코드의 핵심은 answer를 갱신하는 것에 있다.

answer[start][i]를 갱신한다. 즉, 최초로 시작한 node에서 도달 가능한 모든 node를 기록하는 형태이다.

 

나는  경로를 저장해서 모든 노드의 갱신을 한번에 하려고 생각했다.

하지만 제일 처음 bfs로 풀었던 형태를 여러번 시도하면 풀이가 가능한 문제이다.

 

역시 알고리즘은 관성이다. 안하다가 하면 힘들다.