[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

	import java.io.*;
	import java.util.*;
	public class boj_11403 {
	static int[][] matrix;
	static Queue<Integer> queue = new LinkedList<>();
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	StringTokenizer st = new StringTokenizer(br.readLine());
	int n = Integer.parseInt(st.nextToken());
	matrix=new int[n][n]; //인접행렬
	int tmp;
	for(int i=0; i<n; i++) { //입력
	st = new StringTokenizer(br.readLine());
	for(int j=0; j<n; j++) {
	matrix[i][j]=Integer.parseInt(st.nextToken());
	}
	}
	for(int i=0; i<n; i++) {
	for(int j=0; j<n; j++) { //첫번째 행부터 갈 수 있는 길들을 큐에 추가
	if(matrix[i][j]==1) { //갈수 있는 길
	queue.add(j); //큐에 추가
	}
	}
	while(!queue.isEmpty()) { //큐가 비지 않았으면
	tmp=queue.poll(); //큐에 있는 데이터를 꺼낸 뒤 잠시 저장
	BFS(i,tmp); //BFS메소드 호출
	}
	}
	for(int i=0; i<n; i++) {
	for(int j=0; j<n; j++) {
	bw.write(matrix[i][j]+" ");
	}
	bw.write("\n");
	}
	bw.flush();
	bw.close();
	}
	public static void BFS(int i,int tmp) { //시작한 지점 i, 큐에서 나온 변수 tmp
	matrix[i][tmp]=1; // i에서 tmp는 갈 수 있으므로 1로 변경
	for(int j=0; j<matrix[0].length; j++) { //matrix[0].length==n
	if(matrix[tmp][j]==1&&matrix[i][j]!=1) { //matrix[i][j]==1인데 큐에 넣으면 무한루프를 돌게 될 수 있으므로 조건 추가
	queue.add(j); //갈 수 있는 길이므로 큐에 추가
	}
	}
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

풀이

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

한 정점에서 갈 수 있는 길은 인접행렬형태로 입력받기 때문에 정점 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