백준 11403번 경로찾기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Search_Path {
    static int N;
    static boolean flag = false;
    static int[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        int[][] answer = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                boolean[] visited = new boolean[N];
                dfs(i,j,0,visited);
                if(flag){
                    answer[i][j] = 1;
                }
                flag = false;
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(answer[i][j]+" ");
            }
            System.out.println();
        }
    }
    public static void dfs(int start, int end,int count,boolean[] visited){
        if(count>0&&start==end){
            flag = true;
            return;
        }
        for (int i = 0; i < N; i++) {
            if(!visited[i]&&map[start][i]==1){
                visited[i]=true;
                dfs(i,end,count+1,visited);
            }
        }

    }
}

풀이방법

1. 각 맵의 인덱스에서 갈수있는 노드를 완전탐색한다.
2. 방문하지 않은 노드면서, 입력값에서 1을 표시한 노드라면, 방문체크하고 탐색을 계속한다.
3. 목표한 노드에 도착한다면 flag = true 처리를하여 도착 표시를 한다.
   count는 시작 노드와 목표노드가 경로를 거치지 않고 곧바로 탐색을 종료하는것을 방지하기 위해 설정하였다. (ex. 0 -> 1-> 2 -> 0 이 아닌
   0->0 인경우 제외.)
4. 만약 목표노드에 도착 표시가 되어있다면 answer에 1표시를 한다.

후기

처음에 문제가 뭔소린지 이해가 안되서 그림판에다 노드를 그려가며 풀이했다.
확실히 노드,간선 문제는 그림으로 그렸을때 이해가 쉬운것 같다.