문제 이해

i번째 줄의 j번째 숫자가 1인 경우 i ⇒ j로 바로 가는 간선이 존재한다는 의미이다.(즉 인접한 점이다)
반대로 0인 경우 간선이 존재하지 않는다는 의미이다.(즉 인접한 점이 아니다)

이 때, 중간에 거치는 간선의 개수와 상관없이 i ⇒ j로 가는 길이 존재하는 경우 1을 출력하고, 아닐 경우 0을 출력하는 문제이다.

---

문제 풀이

이 문제는 "방향" 그래프이기 때문에, i ⇒ j로 갈 수 있다고 해서 j ⇒ i로 가는 것이 보장되지는 않는다. 즉, 직접 수행해 보는 수밖에 없다.
1, 2, ..., N 모든 점에서 DFS 혹은 BFS를 수행하여, visit 값이 true로 변한 점은 1을 출력하고, 아닐 경우 0을 출력하면 될것이다.

다른 문제와 동일하게, 재귀함수일 경우 visit 값 처리가 조금 복잡해질 것 같아서(새로운 메서드를 만들어서 수행시켜야함) BFS를 통해 문제를 해결하고 한 개 메서드에 visit값 처리까지 포함시켰다.

• 코드 리뷰를 하다 보니 새로운 메서드를 만들어서 visit값 처리를 하는 것이 OOP적으로는 조금 더 좋을 것 같다는 생각이 들었다.(독립성이 높아질 것) 다음부터는 조금 귀찮더라도 새롭게 만들 수 있다면 메서드를 새롭게 만들자.

---

코드

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

public class Main {
	static int N;
	static ArrayList<Integer>[] lists;
	static StringBuilder sb = new StringBuilder();

	static void bfs(int start) {
		Queue<Integer> queue = new LinkedList<>();
		boolean[] visit = new boolean[N];
		
		for(int s:lists[start]) {
			queue.add(s);
		}
		
		while(!queue.isEmpty()) {
			int tmp = queue.poll();
			
			if(visit[tmp]) continue;
			visit[tmp] = true;
			
			for(int s:lists[tmp]) {
				queue.add(s);
			}
		}
		
		for(int i =0;i<N;i++) {
            // start -> i로 가는 길이 존재하는지 확인
			if(visit[i]) sb.append(1).append(" ");
			else sb.append(0).append(" ");
		}
		sb.append("\n");
	}
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();

		N = sc.nextInt();
		
		lists = new ArrayList[N];
		
		for(int i =0;i<N;i++) {
			lists[i] = new ArrayList<>();
		}
		
		for(int i =0;i<N;i++) {
			for(int  j=0;j<N;j++) {
				int tmp = sc.nextInt();
				if(tmp!=0) lists[i].add(j);
			}
		}
		
		for(int i =0;i<N;i++) {
			bfs(i);
		}
		
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과