[백준] 11403 경로 찾기 & 플로이드워샬

Bini by Bini·2023년 3월 17일

BFS DFS 플로이드워셜

코테

목록 보기

18/24

문제

[실버5]
https://www.acmicpc.net/problem/11403

해설 없이 스스로 풀었나요?
X
재풀이 필수, 간만에 그래프 풀어서인지 접근도 제대로 하지 못했ㄷ ㅏ..

아이디어

이 문제는 DFS, BFS, 플로이드워샬 총 세가지 방법으로 풀이할 수 있다.

1. DFS, BFS
DFS, BFS로 어떻게 시작정점에서부터 이동가능한 끝정점까지 모두 1로 바꾸어야 되나 고민했는데.. 바꾸어서 전체 그래프를 완성시킨다는 생각이 아니라,

정점을 0부터 N까지 돌 때마다 visited 배열을 초기화 하고,
현재 시작정점에서 방문가능한 노드를 모두 1로 바꾸고
다음 반복을 진행하기 전에 visited 배열을 출력해주면 되는 것이었다.

2. 플로이드워샬
플로이드 워셜은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우' 사용할 수 있는 알고리즘이다.

곧 플로이드 워셜 알고리즘은 A->B 경로와 A->C->B 경로 중 더 가까운 것을 판별하고 업데이트 해주는 역할을 한다.

그러나 이 문제의 경우 거리를 판별할 필요가 없기 때문에 연결이 가능한지에 대해서만 판단하면 된다.

3중 for문으로 구현하고, 가장 바깥쪽 반복문은 거쳐가는 노드에 대한 제어문이라고 생각하면 된다.

이렇게 노드의 개수가 N개 일 때 알고리즘상으로 N번의 단계를 수행하고,
단계마다 O(N^2)의 연산을 통해 '현재 노드를 거쳐 가는' 모든 경로를 고려한다.
-> 따라서 플로이드 워셜 알고리즘의 총시간 복잡도는 O(N^3)이다.

나동빈 - 플로이드 와샬 알고리즘 이론
https://blog.naver.com/ndb796/221234427842

+또한 처음에 입력받을 때 인접행렬로 주어지지만, 인접리스트로 변경해서 저장해도 된다.

풀이

import sys
sys.setrecursionlimit(10**4)

def dfs(v):
    for k in range(N):
        if graph[v][k] == 1 and visited[k] == 0:
            visited[k] = 1
            dfs(k)
    
N = int(input())

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

answer = [[0 for _ in range(N)] for _ in range(N)]

for i in range(N):
    visited = [0] * N
    dfs(i)
    print(*visited)

import sys
from collections import deque

def bfs(start):
    q = deque([start])
    visited = [0] * N
    
    while q:
        now = q.popleft()
        for k in range(N):
            if graph[now][k] == 1 and not visited[k]:
                visited[k] = 1
                q.append(k)
    print(*visited)

N = int(input())

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

answer = [[0 for _ in range(N)] for _ in range(N)]

for i in range(N):
    bfs(i)

플로이드 워샬

import sys

N = int(input())

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

for k in range(N): # k는 거쳐가는 노드, k를 거치는 간선이 있는지 확인
    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 row in graph:
#     for col in row:
#         print(col, end = ' ')
#     print()

for row in graph:
    print(' '.join(map(str, row)))