[백준/Python] 11403번(그래프 이론, 그래프 탐색, 플로이드-워셜)_경로찾기

📌문제 유형

그래프 이론, 그래프 탐색, 플로이드-워셜 (실버1)

 

📌문제

11403번: 경로 찾기

 

📌나의 문제풀이

n = int(input())
graph = [[] for _ in range(n)]
ans = []

for i in range(n):
    li = list(map(int, input().split()))
    for j in range(len(li)):
        if li[j] == 1:
            graph[i].append(j)

def dfs(start):
    if graph[start] == []:
        return
    
    for num in graph[start]:
        if not visited[num]:
            visited[num] = 1
            dfs(num)

for k in range(n):
    visited = [0] * n
    if graph[k]:
        dfs(k)
    ans.append(visited)

for a in ans:
    print(*a)

 

📌 다른사람의 문제풀이

[백준] 11403 경로찾기 (python 파이썬)

import sys
N = int(input())

adj_matrix = []
for _ in range(N):
    adj_matrix.append([int(x) for x in sys.stdin.readline().rstrip().split()])

for k in range(N):
    for i in range(N):
        for j in range(N):
            if adj_matrix[i][k] == 1 and adj_matrix[k][j] == 1:
                adj_matrix[i][j] = 1

for row in adj_matrix:
    print(' '.join(map(str,row)))

 

 

📌 리뷰 

- '단계마다 거쳐가는 노드'를 연결하는 플로이드 워셜로 코드 작성 가능

- 단, 연결해주는 노드가 바깥 for문에 있어야 빠지지 않고 연결 가능

[이것이 취업을 위한 코딩테스트다 with 파이썬] Ch.9 최단 경로