[ 백준 / 파이썬 ] 11403. 경로 찾기

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

11403번: 경로 찾기

 

🎉🎉 문제

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

 

🎉🎉 풀이

✅ 가중치 없는 방향 그래프를 만들고 모든 좌표마다 이어져있는지 아닌지 탐색해서 그래프를 새로 만들어 출력했다

✅ 처음에 틀렸습니다 떴는데 로직 문제인 줄 알았으나 출력 형식이 문제였다

✅ 성공 뜨고 다른 사람 풀이를 보니 플로이드와샬로 푼 사람들이 많았음 알고리즘 공부 해야지 ...

 

🎉🎉 코드

from collections import deque

n = int(input())

graph = [[] for _ in range(n)] #가중치 없는 방향 그래프 G

for i in range(n):
  vlist = list(map(int, input().split())) #연결 상태를 한줄씩 입력 받는다
  for j in range(n):
    if vlist[j] == 1: #i->j 연결돼있다면
      graph[i].append(j) #방향 그래프에 추가

answer = [[0]*n for _ in range(n)]

for i in range(n):
  for j in range(n):
  
    queue = deque()
    visited = [False]*n
    queue.append(i) #시작점
    
    while queue:
      v = queue.popleft()
      visited[v] = True
      if j in graph[v]: #v가 j와 연결된 정점이라면
        answer[i][j] = 1 #i와 j는 이어져 있으므로 1로 상태를 변경하고
        break # while문 멈춘다
      
      for k in graph[v]: #i와 연결된 정점을 따라가는데
        if not visited[k]: #이전에 방문하지 않은 정점이면
          queue.append(k) #탐색하기 위해 queue에 추가

      
for row in answer:
    for col in row:
        print(col, end = " ")
    print()