[Python] 백준 11403번 경로 찾기 풀이

문제 확인하기

---

11403번: 경로 찾기

 

나의 풀이

---

입력된 그래프를 바탕으로 노드-엣지 사이 연결 관계를 구성했다. 연결 관계를 Queue에 넣어 순차적으로 조회하여, 최종 도달 여부를 확인했다. 다시 돌아오는 경로도 확인해야 하기 때문에, 최초 시작 지점을 visited에 포함하진 않았다.

from collections import deque
import sys


def bfs(node_edge, start, visited):
    queue = deque([start])
    # 큐가 빌 때까지 반복
    while queue:
        node = queue.popleft()
        # 아직 방문하지 않은 경우
        for next_node in node_edge[node]:
            if not visited[next_node]:
                queue.append(next_node)
                visited[next_node] = True
    return visited


def main():
    n = int(input())
    graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
    node_edge = [[] for _ in range(n)]  # 노드-엣지 연결 정보
    # 정답
    answer = [[0 for _ in range(n)] for _ in range(n)]
    # 연결 정보 기록
    for i in range(len(graph)):
        for j in range(len(graph[i])):
            if graph[i][j] == 1:
                node_edge[i].append(j)
    for i in range(len(graph)):
        visited = [False for _ in range(n)]
        # 방문 정보 기록
        visited = bfs(node_edge, i, visited)
        for j in range(len(graph[i])):
            answer[i][j] = 1 if visited[j] else 0
    # 정답 출력
    for row in answer:
        print(" ".join(map(str, row)))


if __name__ == "__main__":
    main()