백준 11403번 경로 찾기

정보

문제 바로가기 [클릭]

난이도: Silver1

관련 개념: #그래프이론 #그래프탐색 #플로이드-워셜

---

조건

시간 제한	메모리 제한
1 초	256 MB

---

문제

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

---

예제 입출력 1

입력

3
0 1 0
0 0 1
1 0 0

출력

1 1 1
1 1 1
1 1 1

---

예제 입출력 2

입력

7
0 0 0 1 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 1 1 0
1 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0

출력

1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 0 0 0 0 0
1 0 1 1 1 1 1
1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 1 0 0 0 0

---

코드(파이썬)

import sys


n = int(sys.stdin.readline())

graph = [list(map(int, line.split())) for line in sys.stdin.readlines()]

for m in range(n):
    for s in range(n):
        for e in range(n):
            graph[s][e] |= graph[s][m] & graph[m][e]
            
for line in graph:
    sys.stdout.write(' '.join(map(str, line)) + '\n')

---

특이사항

• 플로이드-워셜 알고리즘 기초 문제
• 내 코드(30,864KB, 384ms)에 비해 우수한 코드(바로가기, 32,404KB, 104ms)와 비교

  • from sys import stdin
    from collections import deque
    
    
    def bfs(n):
        queue = deque([n])
        while queue:
            k = queue.popleft()
            for i in adjacent_list[k]:
                if not visited_list[i]:
                    queue.append(i)
                    visited_list[i] = True
    
    
    n = int(stdin.readline())
    adjacent_matrix = [list(map(int, stdin.readline().split())) for _ in range(n)]
    adjacent_list = [[] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if adjacent_matrix[i][j] == 1:
                adjacent_list[i].append(j)
    
    for i in range(n):
        visited_list = [False] * n
        bfs(i)
        for j in range(n):
            if visited_list[j]:
                print(1, end=' ')
            else:
                print(0, end=' ')
        print()
    

  • 그래프 갱신 방법
    • 기존: 플로이드-워셜 알고리즘
    • 개선: bfs 이용해 각 노드마다 계산

---

참고문헌

-