백준 11403번(경로찾기) 파이썬

https://www.acmicpc.net/problem/11403

11403번: 경로 찾기

다른 유형만 풀다가 오랜만에 그래프 탐색 문제를 풀어보았다.

오랜만에 하니까 가물가물했다. 

역시 까먹지않게 자주자주 해주는게 좋은거 같다.

아래는 코드와 설명이다.

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10**9) # 재귀제한을 늘려주는건데 이문제에선 필요없다.

n = int(input())
graph = []
for i in range(n):
    graph.append(list(map(int,input().split())))

def dfs(V):
    for i in range(n):
        if visited[i] == 0 and graph[V][i] == 1:
            visited[i]=1
            dfs(i)

for i in range(n):#dfs문을 n 만큼 실행시켜준다.
    visited = [0]*(n) #visited에 dfs()가 실행되어 값들이 저장되어있다
                      # 돌릴때마다 초기화해준다.
    dfs(i)
    for j in range(n): # 저장되어 있는 값들을 출력형식에 맞게 출력해준다.
        if visited[j] == 1:
            print(1, end=' ')
        else:
            print(0,end=' ')
    print() #다음줄로~

이 문제는 찾아보니까 dfs,bfs로도 풀 수 있지만 플로이드-워셜이란 알고리즘으로도 풀 수 있는거 같다.

수업시간에 잠깐 들어본 알고리즘인데 문제로 만나는건 처음이다.

보니까 삼중 for 문을 사용하여 풀던데 그러면 시간이 많이 걸릴거 같아 dfs 문으로 풀었다.