[백준11403번] 경로 찾기 / Python3

문제

가중치 없는 방향 그래프 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 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

예제 출력 2

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

나의 풀이

나는 모든 노드에 대하여 BFS를 돌려 연결되어 있는 곳을 모두 방문하면서 답이 될 answer배열에 1로 변경을 해주겠다는 생각으로 그래프를 입력 받고 별도의 answer라는 똑같은 크기의 2차원 배열을 만들어 answer를 각 노드에 따라 최신화를 시켜주는 방식으로 문제를 풀었다.

예제는 제대로 출력이 나와서 제출을 해보았지만 메모리 초과가 났다. 그래서 혹시 같은 크기의 2차원 배열이 두 개씩이나 선언을 해주어서 그런가 싶어서 (그러나 최대 100 * 100이라 살짝 의심을 품었다.) 처음 그래프를 입력받을 때 인접리스트와 비슷한 형식으로 해당 노드에서 갈 수 있는 노드의 번호만 저장해두는 방식으로 했다. 그러나 똑같이 메모리 초과가 발생했다.

그래서 가만히 생각을 해보니 BFS를 도는 과정에서 방문했던 노드를 또 돈다면 queue의 크기가 너무 커지겠구나라는 생각이 들었고 BFS 함수 안에 visit함수를 두어 방문하였던 노드는 다시 방문을 하지 않게끔 코드를 수정하니 해결되었다.

메모리 초과를 경험하면서 입력받는 그래프에서 메모리를 줄일 수 있었고 덕분에 코드도 더 정리가 되었던 것 같아 좋은 경험이었다는 생각이 들었다.

코드

# 11403번 경로 찾기
import sys
from collections import deque

# bfs
def bfs(N, g, start, answer):    
    q = deque(g[start])
    visit = [False] * N

    while q:
        b_node = q.popleft()
        visit[b_node] = True
        answer[start][b_node] = 1

        for i in range(N):
            if i in g[b_node]:
                answer[b_node][i] = 1

                if not visit[i]:
                    q.append(i)

    return answer

# main
N = int(input())

# 그래프
g = []
for _ in range(N):
    row = [int(x) for x in sys.stdin.readline().split()]
    tmp = []

    for i in range(N):
        if row[i] == 1:
            tmp.append(i)

    g.append(tmp)


answer = [[0 for _ in range(N)] for _ in range(N)]
for node in range(N):
    answer = bfs(N,g,node,answer)

# 출력
for node in answer:
    for i in node:
        print(i, end=' ')
    print()