문제
가중치 없는 방향 그래프 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 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예제 출력 2
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문제 풀이
from collections import deque
n=int(input())
graph=[list(map(int,input().split())) for _ in range(n)]
for k in range(n):
for i in range(n):
for j in range(n):
if graph[i][k]==1 and graph[k][j]==1:
graph[i][j]=1
elif graph[i][j]==1:
graph[i][j]=1
for i in range(n):
for j in range(n):
print(graph[i][j],end=' ')
print()그래프 문제라서 BFS나 DFS 방식으로 풀려고 했는데 도저히 안 풀려서 찾아봤더니 플로이드-워셜 방식을 사용하는 것을 알았다. 이전에 프로그래머스 문제 중 < 순위 > 문제를 풀었을 때 사용한 알고리즘으로 중간노드를 이용하여 경로를 계산하는 로직이다.
이 방식으로 하나씩 차근차근 계산해서 만약 i -> j로 가는 직접적인 경로가 있거나 k 노드를 거쳐서 도달할 수 있는 경로가 있다면 graph에 1을 넣어준다.
플로이드-워셜 방식을 이용하여 풀면서 graph외에 답을 만들기위한 그래프를 새로 선언했는데 그렇게 하니 기존에 있던 경로가 포함이 안됐던 문제가 있었다.
route=[[0]*n for _ in range(n)]
위와 같이 route 그래프를 선언해주고 if문에서 route[i][j]에 1을 넣어주는 방식을 이용했다.
답이 맞지 않아서 route 그래프를 빼고 graph에 값을 넣어주는 방법을 썼다.
다른 사람 풀이
import sys
input=sys.stdin.readline
def BFS(i, arr, n):
visit=[0] * n
q=[i]
while q:
index=q.pop(0)
for i, v in enumerate(arr[index]):
if visit[i] == 0 and v == 1:
visit[i] = 1
q.append(i)
return visit
if __name__ == "__main__":
n = int(input())
arr = []
for _ in range(n):
arr.append([*map(int,input().split())])
for i in range(n):
print(' '.join(map(str,BFS(i,arr,n))))BFS 방식으로도 풀어봐야할 것 같다.
