백준 11403 경로찾기(DFS,BFS, Floyd-Warshall)

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

11403번: 경로 찾기

지금까지 만난 그래프 문제와는 조금 다른점은 방향그래프라는 것이다

 

탐색방법은 매우 다양하며 정점끼리 서로 이어진 것만 새로운 행렬에 체크해줘서 출력하면 되는 문제다

 

DFS

#DFS
#다차원배열 visited을 넘겨서 확인
#std행을 fix시켜놓고 처리를 해야하기 때문에 std 인자를 넣어줬다

def dfs(std, start):
    for i in range(n):
        if visited[std][i] == 0 and board[start][i]:
            visited[std][i] = 1
            dfs(std, i)

n = int(input())

board = [list(map(int,input().split())) for _ in range(n)]
visited = [[0] * n for _ in range(n)]

for i in range(n):
    dfs(i,i)

for i in visited:
    print(*i)

#DFS
#일차원배열 visited을 넘겨서 확인

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

n = int(input())

board = [list(map(int,input().split())) for _ in range(n)]

visited = [0] * n
for i in range(n):
    dfs(i)
    print(*visited) #한 행씩 처리 하기
    visited = [0] * n

BFS

#bfs
from collections import deque

def bfs(start):
    queue = deque()
    queue.append(start)
    while queue:
        a = queue.popleft()
        for i in range(n):
            if not visited[start][i] and board[a][i]:
                queue.append(i)
                visited[start][i] = 1

n = int(input())

board = [list(map(int,input().split())) for _ in range(n)]

visited = [[0] * n for _ in range(n)]
for i in range(n):
    bfs(i)

for i in visited:
    print(*i)

Floyd-Warshall

i를 출발해 j로 바로 가는 것보다

i를 출발해 k를 거쳐 j로 가는 게 효율적일 경우(저렴할 경우) 해당 값을 갱신해주는 것이다

경로 k라 해서 하나의 정점 k만 거치는 것이 아니다

여러 정점을 거치는 모든 경우의 수가 포함되어 있다

#플로이드-워셜 O(n^3)

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


for k in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][k] == 1 and graph[k][j] == 1:
                graph[i][j] = 1

for i in graph:
    print(*i)