경로 찾기

1. 조건

• N : 정점의 갯수 ( 1 <= N <= 100)
• G : 가중치 없는(동일한) 방향 그래프 ( N x N )
  • 0 : (i -> j)간선 없음 / 1 : 간선 있음

2. 출력

• 경로가 있으면 1, 없으면 0으로 인접행렬 형식으로 출력

3. 방식

• BFS의 방식을 사용하여 여러 경로를 거쳐 갈 수 있는지 확인
• 2차원 배열 G에 그 결과를 적용하고 출력 (1번에 갈 수 있는 경우가 G)

4. 코드

# 경로 찾기

from collections import deque  # 덱 사용


def BFS(k):  # BFS 함수 정의
    global point, G

    Q = deque([k])
    check = [0] * N  # 이미 확인한 곳은 가지 않음

    while Q:
        s = Q.popleft()
        check[s] = 1
        for m in arr[s]:
            if m == point:  # 찾던 포인트와 같다면 True(1) 리턴
                return 1
            elif not check[m]:  # 찾던 포인트와 다르고 방문하지 않은 점이라면 추가
                Q.append(m)
    return 0  # 다 돌았다면 간선이 없으므로 False(0) 리턴


N = int(input())
G = [list(map(int, input().split())) for _ in range(N)]
arr = [[] for _ in range(N)]  # G를 변형할 예정이라 방문 가능한 정점을 따로 만듦

for i in range(N):  # 따로 만드는 작업
    for j in range(N):
        if G[i][j]:
            arr[i].append(j)

for k in range(N):  # G에서 갈 수 있다고 표시된 곳을 제외하고 [i][j]를 탐색
    for l in range(N):
        if not G[k][l]:
            point = l  # 포인트 따로 설정
            if BFS(k):
                G[k][l] = 1

for g in G:
    print(*g)

• DFS로도 풀기가 가능하다.