[BOJ][⚪1][백준#11403] 경로 찾기

문제 출처

BAEKJOON Online Judge #11403

문제

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

입력

첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

출력

총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

예제

예제 1

입력

3
0 1 0
0 0 1
1 0 0

출력

1 1 1
1 1 1
1 1 1

예제 2

입력

7
0 0 0 1 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 1 1 0
1 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0

출력

1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 0 0 0 0 0
1 0 1 1 1 1 1
1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 1 0 0 0 0

My Sol

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque

def run(i, s):
    global Q, check

    for v in link[s]:
        if check[i][v]: continue
        check[i][v] = 1
        run(i, v)
    return


N = int(input())
link = [[] for _ in range(N)]
check = [[0]*N for _ in range(N)]
for i in range(N):
    lst = list(map(int, input().split()))
    for j in range(N):
        if lst[j]:
            link[i].append(j)

for i in range(N):
    Q = deque()
    Q.extend(link[i])
    run(i, i)

DFS 방식으로 문제를 풀었다. 무향 그래프가 아닌 방향 그래프이므로, 각 시작점으로부터 어떻게 도착할 수 있을지 확인하기 위해 for문으로 모든 노드를 시작점으로 설정해 가능한 모든 경로를 따져주어야 했다.

인접 행렬은 탐색 시간이 오래 걸릴 것 같아 인접 리스트 link로 데이터를 처리해주었고, visit의 역할이자 i부터 시작해서 도달할 수 있음을 표시하는 check 2차원 배열을 만들었다.

시작점과 해당 depth에서의 기준점을 인자로 받는 run 함수를 만들어, 기준점 s를 link의 인덱스로하는 모든 인접정점 v에 대해 check에 표시되지 않았다면 check에 표시하고 새로운 기준점으로 삼아 run함수를 돌려준다.

그러면 가능한 모든 경로를 check에 찍으면서 조회할 수 있다.

결과

맞았습니다!!