[백준/11403/파이썬] 경로 찾기

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

11403번: 경로 찾기

Problem

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

SOL

BFS나 DFS를 조금 생각해서 구현을 해야하는 문제이다.

 

이 문제의 핵심은 한 노드에서 갈수 있는 곳은 다 보는 문제이다. 즉, 각각 노드별로 연결되어있는 상황을 다 확인해야한다. 여기서, 시작점은 모든 노드라는걸 알 수 있다.

 

예를들어, 아래와 같은 관계를 가진 그래프가 있다고 하자. 인접행렬으로 나타낸다면 , 오른쪽 그림과 같이 될거다.

 

1번 노드에서는, 2번 노드만 연결되어 있지만, 1번 노드에서 도달할 수 있는 지점은 (2,3,4,5) 모든 노드를 방문 할 수 있다.  2번 노드에도 마찬가지로, 인접행렬에서는 3번노드만 연결되어 있는 정보를 갖고있지만, 인접행렬의 정보를 쭉 따라가다 보면, 3,4,5 와 연결되어있는걸 볼 수 있다.

 

그래프를 탐사하는건 DFS/BFS 둘 중에 뭐든 괜찮지만, 이처럼 각 노드에서 한 노드의 모든 연결상황을 보기에는 DFS가 조금 더 와닿게 설계가 되는거 같아서, DFS로 먼저 풀었지만, 나중에 BFS로도 풀어보았음!

 

DFS

# 경로를 찾기
import sys
input= sys.stdin.readline

N=int(input().rstrip())
adj=[list(map(int,input().split())) for _ in range(N)]
#무한 반복을 돌지 않기 위해서, chk 선언
chk=[0 for _ in range(N)]
def dfs(x):
    for i in range(N):
        if adj[x][i] ==1 and chk[i] ==0:
            chk[i] =1
            #한 노드에 대해서 연결되어있다면, 그 연결되어있는 노드로가서, 연결정보 확인
            dfs(i)


for i in range(N):
    dfs(i)
    #탐사가 다 끝나면, chk 배열을 확인해서, 한 노드의 연결정보를 바로 출력한다.
    for j in range(N):
        if chk[j]==1:
            print(1,end=" ")
        else:
            print(0,end=" ")
    print()
    chk=[0 for _ in range(N)]

 

BFS

여기서 흔히 하는 실수가 visited[nx][i]에 방문여부를 chk하는건데, 우리는 잊지 말아야하는게, 한 노드에서 닿을 수 있는 모든 노드를 확인하는 과정이다. 따라서, 최초의 시작점을 기준으로 계속 visited에 기록을 해야한다.

# 경로찾기
# 0->1 ,1->2, 2->1
import sys
from collections import deque
input= sys.stdin.readline

N=int(input().rstrip())
adj=[list(map(int,input().split())) for _ in range(N)]
visited=[[0 for _ in range(N)] for _ in range(N)]
dq=deque()
def bfs(x):
    chk=[0 for _ in range(N)]
    while dq:
        nx=dq.popleft()
        for i in range(N):
            if chk[i] ==0 and adj[nx][i] ==1:
                dq.append(i)
                chk[i]=1
                #이 부분이 핵심. 각 정점(시작점)마다 연결된걸 표시해야한다.
                visited[x][i]=1

for i in range(N):
    dq.append(i)
    bfs(i)

for v in visited:
    print(*v)    
#print(visited)