[BOJ 백준] 11403 경로 찾기 - 자바

• 접근 유형 : dfs
• 접근 방법 : boolean 배열을 일차원 배열로 선언하여, 각 정점에 대해 방문했는지 여부를 확인한다. 모든 정점에 대해 dfs 탐색을 통해 갈 수 있는 노드까지 탐색해본다. 이를 위해 for문에서 boolean 배열을 초기화해주는 작업이 필요하다.

 

 

public class Main_11403 {
	private static int N;
	private static boolean[] visited;
	private static int[][] resultMatrix;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());//정점의 개수
		
		visited = new boolean[N];
		
		resultMatrix = new int[N][N];
		
		StringTokenizer st = null;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int temp = Integer.parseInt(st.nextToken());
				if(temp == 1) {
					resultMatrix[i][j] = 1;
				}
			}
		}
		
		for(int i = 0; i < N; i++) {
			visited = new boolean[N];
			for (int j = 0; j < N; j++) {
				if(resultMatrix[i][j] == 1 && !visited[j])
					search(i, j);
			}
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(resultMatrix[i][j] + " ");
			}
			System.out.println();
		}
		
	}
	
	/**
	 * @param from : 시작 노드
     * @param to : 방문할 노드
	 */
	private static void search(int from, int to) {
		visited[to] = true;
		resultMatrix[from][to] = 1;
		
		for(int i = 0; i < N; i++) {
        	//연결 가능한 노드 중에서 아직 방문하지 않은 노드를 방문함 
			if(!visited[i] && resultMatrix[to][i] == 1) search(from, i);

		}		
	}
	
}