경로 찾기

solved_ac[Class3][경로 찾기](https://www.acmicpc.net/problem/11403)

문제

가중치 없는 방향 그래프 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

문제 해석

[백준]1260번: DFS와 BFS에서 BFS에 대해 자세히 기술해놨으니 확인해보도록 하자.

예제 입력 2 를 보도록 하자. 이걸 graph로 바꾸게 되면

graph = [
[3],
[6],
[],
[4, 5],
[0],
[6],
[2]
]

이런 식으로 나타낼 수 있다.

• 0번째 노드가 갈 수 있는 노드는 3번 노드이다.
  • 3번째 노드가 갈 수 있는 노드는 4, 5이다.
    • 4번째 노드가 갈 수 있는 노드는 0이다.
    • 5번째 노드가 갈 수 있는 노드는 6이다.
      • 6번째 노드가 갈 수 있는 노드는 2이다.

이렇게 되면 0번째 노드는 3, 4, 5, 0, 6, 2 노드를 연결되어 있는 노드들을 거쳐서 갈 수 있다는 것이다. 그것이 예제 출력 2의 첫번째 줄

1 0 1 1 1 1 1 이다. 1번 노드를 제외한 나머지를 갈 수 있다는 뜻이 된다.

이걸 이해했다면 문제는 다 푼것이나 다름이 없다.

풀이

• 위에 문제 해석에서 설명했듯이 입력받은 숫자들을 전부 graph로 바꾸어준다.
• 한쪽이라도 연결되어 있는 노드라면 각 행, 열에 맞게 노드 번호를 집어 넣어준다.
• bfs 함수를 선언한다.
  • 시작 노드 v를 받고 queue에 집어 넣어준다.
  • N x N 행렬에서 1줄을 출력해 줄 visit 변수를 선언한다.
  • visit 변수는 한 노드가 연결되어 있는 노드들을 통해 갈 수 있는 모든 지점을 1로 바꾸어 주는 역할을 한다.
  • 루프
    • queue에서 노드 하나를 꺼내어준다.
    • 해당 노드가 1차적으로 갈 수 있는 노드를 선별하기 위해 루프를 돌려준다.
      • 만약 그 해당 노드를 들른 적이 있으면 넘어가고 들른 적이 없으면 0이기 때문에 1로 바꾸어주고 해당 노드를 queue에 넣어준다.]
      • 그 이유는 시작 노드 v가 연결되어 있는 노드를 통해서 어디까지 갈 수 있는지 조사를 하기 위해서 이다.
      • queue가 빌 때까지 조사를 했다면 해당 노드 하나가 갈 수 있는 모든 경우의 수를 visit 변수에 저장을 해놓았다는 것이다.
      • visit 변수를 한 줄에 출력해준다.
• bfs 함수는 한 노드가 갈 수 있는 경우의 노드들을 출력해 주는 것이다.
• N x N 행렬이기 때문에 0번 노드부터 N - 1번 노드까지 bfs 함수를 돌려주면 된다.

import sys
from collections import deque

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

graph = [[]for _ in range(N)]
queue = deque()

for i in range(N):
    a = list(map(int, sys.stdin.readline().split()))
    for j in range(N):
        if a[j] == 1:
            graph[i].append(j)  
               
def bfs(v):
    queue.append(v)
    visit = [0] * N
    while queue:
        a = queue.popleft()
        for i in graph[a]:
            if visit[i] == 0:
                visit[i] = 1
                queue.append(i)
    for i in visit:
        print(i, end = " ")

for i in range(N):
    bfs(i)
    print()