백준 11403번: 경로 찾기

https://www.acmicpc.net/problem/11403

 

방향 그래프가 주어진 상태에서 정점 i에서 j까지 가는 경로의 존재 여부를 확인하는 문제이다.

 

구현하기 보다 편한 DFS로 탐색을 했다.

원래는 DFS 시작에 visited에 넣어주었는데,

이번 문제에서는 시작지점으로 다시 돌아오는 것까지 확인해야하기 때문에

visited에 넣어주는 것은 DFS 내부에서 다음 DFS로 넘어가기 전에 넣어주는 것으로 해결했다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.HashSet;

public class Main {
  static ArrayList<Integer>[] nodes;
  static HashSet<Integer> visited;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    nodes = new ArrayList[N];
    for (int i = 0; i < N; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      nodes[i] = new ArrayList<>();
      for (int j = 0; j < N; j++) {
        if ( st.nextToken().equals("1") ) nodes[i].add(j);
      }
    }

    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < N; i++) {
      visited = new HashSet<>();
      DFS(i);
      for (int j = 0; j < N; j++) {
        if ( visited.contains(j) ) sb.append("1 ");
        else sb.append("0 ");
      }
      sb.append("\n");
    }

    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    bw.write( sb + "" );
    bw.flush();
    bw.close();
  }

  static void DFS(int i) {
    for (int node : nodes[i]) {
      if ( visited.contains(node) ) continue;
      visited.add(node);
      DFS(node);
    }
  }
}