경로 찾기

11403번: 경로 찾기

 

나의 풀이

from collections import deque
import sys
input = sys.stdin.readline

def conn_check(conn_dict, start, end, len_map):
    queue = deque([start])
    visit = [0]*len_map
    while queue:
        n_p = queue.popleft()
        
        for next_p in conn_dict[n_p]:
            if visit[next_p] == 0:
                visit[next_p] = 1
                queue.append(next_p)
    if visit[end] == 1:
        return '1'
    else:
        return '0'

n_ct = int(input())
conn_dict = {i:[] for i in range(n_ct)}
for i in range(n_ct):
    n_list = list(map(int, input().rstrip().split()))
    for j in range(len(n_list)):
        if n_list[j] == 1:
            if i not in conn_dict:
                conn_dict[i] = [j]
            else:
                conn_dict[i].append(j)

for i in range(n_ct):
    result = []
    for j in range(n_ct):
        result.append(conn_check(conn_dict, i, j, n_ct))
    print(' '.join(result))

 

시간 복잡도

for i in range(n_ct) : 이중 for문 ( 이차형 시간 복잡도 )
    result = []
    for j in range(n_ct):
        conn_check(a,b,c,d) : bfs 함수 ( 이차형 시간 복잡도 )
해당 알고리즘은 시간 복잡도는 사차형 시간 복잡도 ( O(n**4) )