<Algorithm> 62. 11403번 경로찾기

1. 11403번 경로찾기

• 기본 BFS 문제, 방향성이 없는 그래프이기 때문에 다시 자신으로 돌아오는 부분만 해결하면 되는 문제

• BFS문제를 풀지않다가 다시 해보니 헷갈리는 부분이 있었다. 한번씩 복습 겸 하는게 좋을 것 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static boolean[] visited;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        ArrayList<Node>[] aLists = new ArrayList[N];
        for(int i = 0 ; i < N; i++)
            aLists[i] = new ArrayList<>();
        
        for(int i = 0; i < N; i ++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++) {
                int k = Integer.parseInt(st.nextToken());
                if(k != 0) {
                        aLists[i].add(new Node(j));
                }    
            } 
        }
        
        for(int i = 0; i < N; i ++) {
            for(int j = 0; j < N; j++) {
                visited = new boolean[N];
                System.out.print(bfs(i, j, aLists)+" ");
            }
            System.out.println();
        }
 
        
        
    
    }
    public static int bfs(int i, int j,ArrayList<Node>[] alist) {
        Queue<Node> queue = new LinkedList<>();
        
        queue.add(new Node(i));
        
        while (!queue.isEmpty()) {
            Node node = queue.remove();
            
            int x = node.x;
            
             visited[x] = true;
            
            for(Node no : alist[x]) {
                
                if(i == j && no.x == i) {
                    return 1;
                } // 다시 되돌아올때 
                
                if(!visited[no.x]) {
                    
                    if(j==no.x) {
                        return 1;
                    }else {
                        queue.add(new Node(no.x));
                    }
                }
            }
        }
        return 0;
        
    }
    
    
}
class Node{
    int x;
    public Node(int x) {
        super();
        this.x = x;
    }
}