[백준] 11403 경로 찾기 - Java

 

 

 

행렬 형태로 주어진 그래프를 이용해 탐색을 수행해야 한다.

 

행에 대해서 bfs를 돌린 후 해당하는 행이 접근할 수 있는 열을 기록하고 출력한다.

 

주어진 조건에서 i,i에 해당하는 좌표는 무조건 0으로 주어진다고 했으니, visit를 체크할 때 주의하자. 

 

 

import java.util.*;
import java.io.*;

public class Main {

    static int N;        

    static int[][] map;
    static boolean[] visit;   
    
    static StringBuilder sb = new StringBuilder();
        

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
            
        map = new int[N+1][N+1];
        
        for(int i=1; i<N+1; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1; j<N+1; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 1; i<N+1; i++){
            bfs(i);
        }

        System.out.println(sb);    

    }
    static void bfs(int x){
        Queue<Integer> q = new LinkedList<>();
        visit = new boolean[N+1];        
        q.add(x);
        
        
        visit[x] = false;

        while(!q.isEmpty()){
            int tmp = q.poll();

            for(int i=1; i<N+1; i++){
                if(map[tmp][i] == 0){
                    continue;
                }
                if(visit[i]){
                    continue;
                }

                q.add(i);
                visit[i] = true;
            }
            
        }

        for(int i=1; i<N+1; i++){
            if(visit[i]){
                sb.append(1 + " ");
            }else{
                sb.append(0 + " ");
            }
        }
        sb.append("\n");


    }
}