(Python) - BOJ(11403번) : 경로 찾기

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

11403번: 경로 찾기

---

• 해설 : 

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

 

 

 

---

• 풀이 :

그래프에서 인접한 모든 노드들을 탐색하는 BFS 또는 DFS를 사용하여 j노드와 연결되어있는지 찾으면 된다.

 

 

 

---

• 소스코드 : 

 

import sys
from collections import deque
input = sys.stdin.readline
 
def find(start,board):
    queue = deque([start])
    check = [0 for _ in range(N)]
    #check[start] = 1
    while queue:
        x = queue.popleft()
        for i in range(N):
            if board[x][i] == 1 and check[i] == 0:
                #print(i,start)
                queue.append(i)
                check[i] = 1
    return check
 
 
 
 
if __name__ == "__main__":
    N = int(input())
    board = [list(map(int,input().split())) for _ in range(N)]
    ans = []
    for i in range(N):
        print(' '.join(map(str,find(i,board))))