[백준 11403] 경로 찾기 Python

경로 찾기

티어 : Silver 1
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 그래프 이론, 그래프 탐색, 플로이드-워셜

 

문제

가중치 없는 방향 그래프 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으로 출력해야 한다.

 

예제 입출력

반응형

---

Algorithm

DFS
1. 그래프 구현
2. DFS 돌면서 갈 수 있는 곳 리스트에 저장
3. 리스트에 들어있는 곳에 맞게 1로 변경

 

Code

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def dfs(x):
    global idx
    # 현재 노드에 방문한 적 있는지 확인
    if visited[x]:
        return False
    
    # 방문 기록
    # dfs를 첫 번째 수행하는 경우가 아닐 때만 수행
    if x != idx or (nodes and x == idx):
        visited[x] = True
        nodes.append(x)
    
    # 인접 노드 방문
    for next_node in graph[x]:
        dfs(next_node)
    
    return True

def set_answer(i):
    for j in nodes:
        answer[i][j] = 1
        
N = int(input())
matrix = [list(map(int, input().split())) for _ in range(N)]
answer = [[0 for _ in range(N)] for __ in range(N)]
# 그래프 구현
graph = [[] for _ in range(N+1)]
for i in range(N):
    for j in range(N):
        if matrix[i][j] == 1:
            graph[i].append(j)

# 모든 정점 DFS 돌기
for idx in range(N):
    nodes = []
    visited = [False for _ in range(N+1)]
    
    if dfs(idx):
        # set answer
        set_answer(idx)

for i in range(N):
    print(' '.join(map(str, answer[i])))

메모리: 30840 KB
시간: 92 ms