💻 백준 11403: 경로 찾기

문제 소개 🧐

가중치 없는 방향 그래프 G가 주어졌을 때
모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 문제

입력 📝

  • 첫째 줄에 정점의 개수 N이 주어져
  • 둘째 줄부터 N개의 줄에는 그래프의 인접 행렬이 주어져
  • i번째 줄의 j번째 숫자가 1이면 i에서 j로 가는 간선이 존재한다는 의미

출력 📤

  • 총 N개의 줄에 걸쳐 문제의 정답을 인접 행렬 형식으로 출력
  • 정점 i에서 j로 가는 경로가 있으면 1, 없으면 0으로 출력

제한 ❌

  • 시간: 1초
  • 메모리: 256 MB
  • 정점 N: 1 ≤ N ≤ 100

첫 번째 시도: BFS 탐색 🚀

Idea

N의 범위가 100으로 작은 편이라
모든 정점에서부터 탐색을 시작해도 시간 안에 충분히 통과할 수 있을거라 생각했다

그래서 각 정점 i에서 시작해서
i와 연결된 모든 노드를 방문하는 방식으로 접근했다

i에서 갈 수 있는 모든 경로를 너비 우선 탐색(BFS)처럼 찾아내
방문 여부를 기록하는 visited_li 리스트를 만들었고
이 리스트가 그대로 정답 행렬의 한 행이 될거라 예상했다

그래프는 인접 리스트 형태로 표현하기 위해 딕셔너리를 활용했다

Code

import sys
from collections import deque

n = int(sys.stdin.readline().rstrip())
s = [list(map((lambda x: False if x=='0' else True), sys.stdin.readline().split())) for _ in range(n)]
queue = deque()

# 그래프를 인접 리스트(딕셔너리)로 표현
gr = dict()
for i in range(0, n):
    li = list()
    for k in range(n):
        if s[i][k]:
            li.append(k)
    gr[i] = li

ans = []
# 모든 정점에서 탐색 시작
for i in range(n):
    queue = deque(gr[i])
    visited_li = [False for _ in range(n)]
    while queue:
        v = queue.pop()  # i가 방문하는 노드 v

        if not visited_li[v]:
            visited_li[v] = True
            for num in gr[v]:  # i가 방문한 v가 방문한 num 추가
                queue.appendleft(num)
                 
    ans.append(visited_li)

for li in ans:
    print(*map(int,li))

Result

  • 성공! 🎉
  • 오랜만에 한 번에 문제를 해결해서 기분이 좋았다

개선할 부분 🤔

  • 현재 풀이는 모든 정점에 대해 BFS/DFS를 수행하는 방식
  • 알아보니 이 문제는 플로이드-워셜 알고리즘의 대표적인 예시이기도 하다
  • 다음엔 플로이드-워셜로도 풀어보면 좋을 것 같다