[백준 11403번] 파이썬 - 경로 찾기

http://www.acmicpc.net/problem/11403

11403번: 경로 찾기

 

# 조건

• 정점의 개수 N
• N개 줄에는 그래프의 인접 행렬이 주어진다.
• i번째 줄의 j번째 숫자가 1인 경우 i에서 j로 가는 간선이 존재한다는 뜻
• 총 N개의 줄에 걸쳐 문제의 정답을 인접행렬 형식으로 출력

 

# 접근 방법 및 Solution

• 모든 그래프에 대한 정점을 받은 후 결과를 저장해줄 배열 만들기
• 이후 bfs를 이용하여 접근 가능한 정점 들을 기록해준다.
• 전형적인 bfs 문제로서 순회가 가능한 것을 체크하기 위하여
• 시작 지점에 1을 해주지 않는 것이 중요하다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  
  
def bfs(n):  
    global result  
    q = deque()  
    start = n  
    q.append(n)  
    while q:  
        sti = q.popleft()  
        for j in range(len(matrix[sti])):  
            if matrix[sti][j] == 1 and visited[j] == 0:  
                q.append(j)  
                visited[j] = 1  
                result[start][j] = 1  
  
  
  
N = int(input())  
  
matrix = [[*map(int, input().split())] for _ in range(N)]  
  
result = [[0]*N for _ in range(N)]  
for i in range(N):  
    visited = [0] * N  
    bfs(i)  
  
for k in result:  
    print(*k)