[백준] 경로 찾기 (java) Bfs

2020-03-03

경로 찾기 (백준> Dfs_Bfs)

문제 링크

문제설명

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


풀이

package Dfs_Bfs;

import java.util.*;

public class beak_경로찾기 {
	
	public static void main(String[] args) {
		Scanner sc  = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int arr[][] = new int[n][n];
		Queue<Integer> q = new LinkedList<Integer>();
			
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++)
				arr[i][j] = sc.nextInt();
		}
		
		
		for(int i=0;i<n; i++) {
			for(int j=0; j<n; j++) {
				if(arr[i][j] == 1) {//i행부터 갈 수 있는 길들을 큐에 추가 
					q.add(j);
				}
			}
			
			//bfs -> i층인 동안 1로 연결된 곳 다 찾아들어가서 1로 만들어준다!
			while(!q.isEmpty()) {
				int temp = q.poll();
				
				arr[i][temp] =1;	//i에서 tmp는 갈 수 있으므로 1로 변경
				for(int j=0; j<arr.length; j++) {
					if(arr[temp][j] ==1 && arr[i][j] !=1) //arr[i][j]==1인데 큐에 넣으면 무한루프를 돌게 될 수 있으므로 조건 추가
						q.add(j);
				}
				
			}
		}//out for
		

		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++)
				System.out.print(arr[i][j]+ " ");
			System.out.println(); // println.(" ") -> 이거했다고 출력형식이 잘못됐다고 뜸...;
		}
		
	}

}

후기 (1h)

처음에는 밑에처럼 DFS로 풀려고했는데, 그렇게 하다보니 X와 Y가 꼬이고 배열을 새로 만들면서 문제가 발생했다… BFS로 풀면서도 X Y를 잘 설정해줬어야 했는데 한번 이해하고 보니 다시 풀 수 있을 것 같았다!!

새로운 DFS/BFS 문제에 얼탈뻔했다..

원래 풀려던 방식


	//그 값으로 돌아오면 1, 못돌아오면  0을 return 한다
	//x행이 y랑 연결돼있으면 타고 넘어가
	
	static int dfs(int arr[][], int x, int y) {
//		System.out.println("arr[" +x +"][" + y+ "] =" + arr[x][y] + "y" + y);
		
		if(arr[x][y] == y)
			return y;
		
		else {
			for(int i=0; i<arr.length; i++) {
				if(arr[x][i] != -1)
					dfs(arr,i,y);
			}			
			return 0;
		}
		
	}
	
	public static void main(String[] args) {
		Scanner sc  = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int arr[][] = new int[n][n];
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++)
				arr[i][j] = sc.nextInt();
		}
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++)
				if(arr[i][j] == 1)
					arr[i][j] = j;
				else
					arr[i][j] = -1;
		}
		
		
		int ans[][] = new int[n][n];
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				System.out.println("??" + dfs(arr,i,j));
				ans[i][j] = dfs(arr,i,j);
			}
		}

		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				System.out.print(ans[i][j] + " ");
			}
			System.out.println(" ");
		}
		
	}