[BOJ] 백준 11403 경로찾기-java

문제

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

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

풀이

반향그래프의 한 점에서 임의의 점을 갈 수 있는 경로가 있는지 판별하는 문제입니다.

한 정점에서 갈 수 있는 길은 인접행렬형태로 입력받기 때문에 정점 a에서 갈 수 있는 모든 정점을 찾으려고 할 때 a에서 연결된 정점이 c,d라고 가정해봅시다.

a는 a와 연결된 c,d에 갈 수 있고 c와 연결된 e라는 점에도 갈 수 있습니다. 

a-c-e 이러한 경로가 존재하기 때문이죠.

이러한 방법으로 갈 수 있는 정점을 모두 찾으려고 할 때 너비 우선 탐색(BFS, Breadth-First Search) 알고리즘을 쓰는 방법이 있습니다.

너비우선 탐색에 대한 설명은 아래 참고할만한 블로그 링크를 남기겠습니다.

일단 한 정점에서 갈 수 있는 경로가 존재하는 정점들을 인접행렬에 1로 표시해야 하기때문에 한 행씩 접근합니다. 

한 행에 있는 1의 개수는 그 점과 인접한 정점의 개수이므로 그 정점을 큐에 넣습니다.

그 후 큐에 있는 데이터를 빼서 BFS 메소드에 넣는데 뺀 데이터의 행을 검사해서 1인 정점을 또 큐에 넣는 작업입니다.

이렇게 결국 한 정점에서 갈 수 있는 경로를 다 찾는데 만약 찾은 정점이 이미 i라는 정점에서 갈 수 있는 점(인접행렬에 1이라고 표시)이라고 표시되어 있으면 그 정점은 큐에 넣지 않습니다.

큐에 넣게 되면 갔던 경로를 무한히 돌게 되어 무한루프를 돌 수 있습니다.

그렇게 모든 정점에 대해서 BFS를 하면 경로찾기 행렬이 완성됩니다.

BFS란? https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html