문제

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

해결

Shortest Path의 문제 유형이고, 나는 bfs의 방법으로 풀었다. visited[]를 통하여 방문할 수 있는 지 없는 지를 계속 확인해준다. 만약 방문할 수 있다면, 해당 j번째 노드에서도 또 어디어디를 갈 수 있는 지 계속 확인해준다.

코드

import sys
from collections import deque

n = int(sys.stdin.readline().rstrip())
graph = []

# 입력값
for i in range(n):
    arr = list(map(int,sys.stdin.readline().split()))
    graph.append(arr)


# 해당 i번째 줄 탐색 
def bfs(i):
	# 방문할 수 있는 지 여부 확인
    visited = [0 for i in range(n)]
    q = deque([i])

    while q:
        x = q.popleft()
        for i in range(n):
            if graph[x][i] == 1 and visited[i] == 0:
                q.append(i)
                visited[i] = 1

    return visited


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