BOJ - 11403

백준 문제 링크
경로 찾기

❓접근법

1. BFS를 사용했다.
2. 함수 안에서 해당 정점이 연결되어 있다면 check.
3. 간선이 존재한다면 visited에 방문 처리한다.
4. for(N)동안 bfs를 실행한 후 인접행렬 형식으로 출력

👌🏻코드

from collections import deque   # BFS방식
N = int(input())
lst = []

for i in range(N):
    x = list(map(int, input().split()))
    lst.append(x)
    
    
visited = [[0] * N for _ in range(N)]


def bfs(x):
    queue = deque()
    queue.append(x)
    
    check = [0] * (N+1)
    
    while queue:
        v = queue.popleft()
        
        for i in range(N):
            if lst[v][i] == 1 and check[i] == 0:
                check[i] = 1
                visited[x][i] = 1
                queue.append(i)
                
                
for i in range(N):
    bfs(i)

    
for i in range(len(visited)):
    print(* visited[i])

공부하던 중 플로이드-워셜 알고리즘에 대해 배울 수 있었는데,
모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용이 가능

플로이드-워셜 알고리즘을 적용한 코드는 아래와 같다.

# 플로이드-워셜 방식
N = int(input())
lst = []

for i in range(N):
    x = list(map(int, input().split()))
    lst.append(x)
    
for i in range(N):
    for j in range(N):
        for k in range(N):
            
            if lst[j][i] and lst[i][k]:
                lst[j][k] = 1  
                
for i in range(len(lst)):
    print(* lst[i])

다만 시간복잡도가 O(N^3)이므로 N이 충분히 작을 때 사용해야 좋을 것 같다.