백준 11403 - 경로 찾기

Java

11403 번 - 경로 찾기

문제

접근 방법

DFS를 사용하였다.
0부터 n-1까지 각 점에서 시작하여, 타고 타고 들어갈 때 마다 방문하였던 노드를 기록한다.
기록 된 노드는 방문을 하였다고 출력을 하여 해결하였다.

주의할 점은, 처음 방문할 때는 방문 체크를 하지 않는다.
이유는, 다른 노드를 통해 와야, 방문한 것이기 때문이다.

코드

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

public class Main {
	static int n, result;
	static boolean[] vis;
	static int[][] adj;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());

    	adj = new int[n][n];

    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < n; j++) {
    			adj[i][j] = stoi(stk.nextToken());
    		}
    	}
    	StringBuilder sb = new StringBuilder();
    	for(int i = 0; i < n; i++) {
    		vis = new boolean[n];
    		DFS(i, true);

    		for(int j = 0; j < n; j++) {
    			if(vis[j])
    				sb.append(1).append(" ");
    			else
    				sb.append(0).append(" ");
    		}
    		if(i != n - 1)
    			sb.append("\n");
    	}
    	System.out.println(sb.toString());
    	br.close();
	}

	static void DFS(int start, boolean first) {
		// 처음에는 자기 자신을 방문 처리를 하지 않는다.
		if(!first)
			vis[start] = true;

		for(int i = 0; i < n; i++) {
			if(!vis[i] && adj[start][i] == 1) {
				DFS(i, false);
			}
		}
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점