[백준] [파이썬] [Graph] [BFS] [DFS] 11403번: 경로 찾기

문제 보러 가기

문제

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

 

import sys 
from collections import deque

if __name__=='__main__':
    N=int(input())
    graph=[list(map(int, input().split())) for _ in range(N)]
    ans=[[0]*N for _ in range(N)]     # 주어진 graph랑 똑같은 모양의 행렬, 정답
    
    for node in range(N):  # 0번 정점부터 N-1번 정점을 다 확인, 정점이 몇개인지 알기 때문에 정점을 기준으로 정보를 확인한다.
        Q=deque()
        Q.append(node)
        while Q:
            n=Q.popleft()               # 현재 노드 n
            for col in range(N):      # NxN, 열 정보를 확인 
                if graph[n][col]==1 and ans[node][col]==0 :  # 정점n과 열 정보 col 정점이 연결(1) 되어 있고 node에서 col을 처음 확인하는경우
                    Q.append(col)                         # 연결된 다음 정점으로 이동 
                    ans[node][col]=1                         # 정점이 간선을 통해 연결되면 1 
        
        print(*ans[node])

 

 

---

 

DFS로 푼 방법

 

import sys 
from collections import deque

def DFS(n):
    global node
    for col in range(N):  # 정점 node, n에 대해 열 정보 즉, 다른 노드와 연결된 상태를 확인 
        if ans[node][col]==0 and graph[n][col]==1: # 중복을 피하기 위해 첫 방문이고, 주어진 정보 graph에서 서로 연결되어 있다면
            ans[node][col]=1 
            DFS(col)

if __name__=='__main__':
    N=int(input())
    graph=[list(map(int, input().split())) for _ in range(N)]
    ans=[[0]*N for _ in range(N)]     # 주어진 graph랑 똑같은 모양의 행렬, 정답

    for node in range(N):  # 0번 정점부터 N-1번 정점을 다 확인, 정점이 몇개인지 알기 때문에 정점을 기준으로 정보를 확인한다.
        DFS(node)
        print(*ans[node])

 

---