[백준 11403] 경로 찾기

문제

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

 

입력

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

 

출력

정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

---

접근

입력에서 주어진 정보로 그래프를 그리면 방향 그래프가 된다. 

먼저 y축의 번호를 기준으로 탐색을 진행한다. 이때 방문 표시를 해서 무한루프가 돌지않도록 해야하는데 이를 출력할 맵에 표시를 한다.

만약 1번노드에서 출발을 하여 3을 거치고 2를 거쳐서 1로 온다고 하면 (1, 3), (1, 2), (1, 1)에 1로 표시를 하여 방문 표시를 한다. 탐색을 하다가 해당 좌표에 1이면 이미 방문한 것이다.

 

정리를 하면 1번 노드가 방문할 수 있는 노드들을 1번째 줄에 출력을 해야하기 때문에 bfs를 시작하는 노드의 번호가 출력맵의 y축 좌표가되어 방문 표시를 한다.

 

구현

문제에서 주어진 입력을 받으며 2차원 리스트 output을 0으로 초기화한다. 

이 리스트는 방문표시를 하고 최종 출력을 할 리스트다.

N = int(input())
matrix = [list(map(int, input().split())) for _ in range(N)]
output = [[0 for _ in range(N)] for _ in range(N)]

 

각 번호를 bfs에 전달한다. 전달된 번호는 고정된 y축 좌표가된다.

for idx in range(N):
    bfs(idx)

 

bfs를 실행한다.

만약 방문을 했다면 전달받은 y축 좌표에 연결된 노드가 x 좌표가 되어 해당 좌표를 1로 표시한다.

def bfs(node):
    q = deque()
    q.append(node)

    while q:
        n = q.popleft()
        for i in range(len(matrix[n])):
            if matrix[n][i] and output[node][i] == 0:
                q.append(i)
                output[node][i] = 1

 

최종적으로 output에는 i번째 노드가 방문할 수 있는 곳들이 담겨져있다.

for y in range(N):
    for x in range(N):
        print(output[y][x], end=" ")
    print()

---

전체 코드

import sys
from _collections import deque

input = sys.stdin.readline

def check_range(y, x):
    return (y>=0 and y<N) and (x>=0 and x<N)

def bfs(node):
    q = deque()
    q.append(node)

    while q:
        n = q.popleft()
        for i in range(len(matrix[n])):
            if matrix[n][i] and output[node][i] == 0:
                q.append(i)
                output[node][i] = 1

N = int(input())
matrix = [list(map(int, input().split())) for _ in range(N)]
output = [[0 for _ in range(N)] for _ in range(N)]

for idx in range(N):
    bfs(idx)

for y in range(N):
    for x in range(N):
        print(output[y][x], end=" ")
    print()