[Python] 백준 11403번 - 경로 찾기

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

11403번: 경로 찾기

 

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 그래프 이론
 - 그래프 탐색
 - 플로이드-워셜

문제

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

 

---

가중치가 없는 단방향의 그래프이며

노드 간의 모든 방향을 확인해야 하기 때문에 반복적으로 확인해야 하는 문제이다.

 

처음에 나는 플로이드 워셜 방법은 생각 못하고 큐를 이용한 bfs로 풀었다.

 

import sys
input = sys.stdin.readline
from collections import deque

n = int(input())
dir = []
for i in range(n):
  dir.append([])
  lst = list(map(int, input().split()))
  for j in range(len(lst)):
    if lst[j] == 1:
      dir[i].append(j)

def check(a, b):
  q = deque()
  q.append(a)
  result = 0
  visited = [0] * n
  while q:
    now = q.popleft()
    visited[now] = 1
    if dir[now]:
      for i in dir[now]:
        if i == b:
          result = 1
          break
        if visited[i] == 0:
          q.append(i)
    if result == 1:
      break
  return result
  
for i in range(n):
  for j in range(n):
    print(check(i, j), end=' ')
  print()

 

방문노드를 표시하고 값을 찾으면 종료하여 리턴하는 방식으로

 

문제를 보자마자 떠오른 제일 간단한 방법으로 풀었다.

 

이후 문제를 다 푼 후 알고리즘 분류를 열어보니 플로이드 워셜로 풀 수 있는 문제여서 한번 더 풀었다.

 

---

 

우선 플로이드 워셜은

2022.11.17 - [Algorithm/이것이 코딩테스트다] - [Python][이코테] 최단경로/ 플로이드 워셜 알고리즘

[Python][이코테] 최단경로/ 플로이드 워셜 알고리즘

특정 수를 지나가는 과정을 확인하는 알고리즘이다.

 

import sys
input = sys.stdin.readline
from collections import deque

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

for k in range(n):
  for i in range(n):
    for j in range(n):
      if data[i][k] == 1 and data[k][j] == 1:
        data[i][j] = 1

for i in range(n):
  for j in range(n):
    print(data[i][j], end=' ')
  print()

 

시간은 bfs로 푼게 더 빨랐고

 

메모리는 플로이드 워셜이 조금 더 적게 먹었다.

 

git 백준 11403번 - 경로 찾기.py