[백준/Python] 11403. 경로 찾기

📌문제 유형: 그래프 이론 

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

 

 

 

📌풀이 

 

문제의 조건을 분석하면, 아래와 같이 볼 수 있다. 

1. 방향 그래프 

2. i->j로 가는 방법이 있는지를 모든 정점에 대해 알아봐야 함. 

 

이때 한 방향으로 계속 깊게 파고 들어야 하니 DFS가 맞다고 판단했다. 

 

각 정점에 대해서, dfs()를 수행하고 갈 수 있는 정점이면 output 1차원 배열에 저장하면 된다. 

하나의 정점 n에 대해 output = [0] * N으로 정의되어 있고, 

graph[n][i] == 1 (갈 수 있는 길이 있고), output[i] == 0 (아직 방문 안했으면) 그 정점 i에 대해 dfs()를 재시행한다. 

 

이걸 모든 정점에 대해 반복하면 완성 !! 

 

⭐ 아이디어: output을 각 정점마다 새로 정의하면 된다는 거. 꼭 하나의 2차원 배열에 넣지 않으려고 해도 된다는 거?

 

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
# output = [[0 for _ in range(N)] for _ in range(N)]
output = [0 for _ in range(N)]
def dfs(n):
    for i in range(N):
        if graph[n][i] == 1 and output[i] == 0:
            # output[n][i] = 1 이렇게 하면 도돌이표, 각 점에 대한 output이 필요
            output[i] = 1
            dfs(i)


for i in range(N):
    dfs(i)
    for j in range(N):
        print(output[j], end = ' ')
    print()
    output = [0 for _ in range(N)]