백준 11403번 경로 찾기

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

1. 인접행렬을 입력받고 결과를 기록할 2차원배열 result를 생성

2. 정점의 갯수반큼 반복

각 정점별로 bfs 샐행하며 한정점에서 갈수있는 정점을 result 배열에 표시.

3. result 배열 출력

이렇게 풀었다. 그래프 캄색에는 bfs를 사용하였다.

주의 할 점이 있는데 한 정점에서 자기자신은 그냥 바로 1을 체크 하는것이 아니고, 다른 정점을 거쳐서 방문이 가능한 경우에만 1로 체크해주어야 한다.

아래는 소스코드이다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
    static int n;
    static boolean[] visited;
    static int[][] injub;
    static int[][] result;
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        injub = new int[n][n];
        result = new int[n][n];
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                injub[i][j] = sc.nextInt();
            }
        }
        
        for(int i=0; i<n; i++) {
            visited = new boolean[n];
            bfs(i);
        }
        
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                System.out.print(result[i][j] + " ");
            }
            System.out.println();
        }
        
    }
    
    static public void bfs(int start) {
        
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(start);
        
        while(!q.isEmpty()) {
            int current = q.poll();
            
            for(int i=0; i<n; i++) {
                if(injub[current][i]==1 && visited[i]==false) {
                    visited[i] = true;
                    q.offer(i);
                    result[start][i] = 1;
                }
            }
        }
    }
    
}