백준 : 경로 찾기 (DFS)

이번문제도 DFS를 사용하면 되는 문제입니다.

 

문제를 풀면서 주의해야 할점에 대해 적어보도록 하겠습니다.

 

1. 입력하는 그래프가 양방향인지, 단방향 그래프인지 꼭!!! 확인해야한다. -> 양방향인줄 알고 조금 시간이...지체... 젠자..ㅇ
2. 각, 시작점(i)/목표점(j)을 기준으로 두고 DFS를 반복적으로 한다.
   1. 단, 반복적으로 진행할때 방문배열은 초기화해야합니다.
   2. 목표에 도달하면, 플레그를 변경하여 도달확인
3. 노드는 1번부터 시작하므로, 노드번호 주의 (모드 노드를 -1해서 생각하면 쉽다.)

package com.controller;

import java.util.*;

public class Main {

	static int n;
	static boolean[] visited ;
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	static int[][] result;
	static boolean flag = false;

	public static void dfs(int now, int target) { //자기자신 도달 주의
		visited[now] = true; //방문표시
		
		for(int i=0; i<graph.get(now).size(); i++) { 
			int tmp = graph.get(now).get(i);
			
			if(target == tmp) { //목표에 도달했다면
				flag = true; //플레그 변경
			}
			
			if(visited[tmp] == false) { //아직방문전이라면
				dfs(tmp, target); //재귀
			}
		}

	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		sc.nextLine(); // 버퍼

		visited = new boolean[n]; //방문 초기화, 인덱스 0부터*****
		result = new int[n][n];
		
		for (int i = 0; i < n; i++) { // 그래프 초기화
			graph.add(new ArrayList<Integer>()); 
		}

		for (int i = 0; i < n; i++) { // 입력값: 인덱스는 0부터 시작이므로 숫자마다 -1하여 삽입
			String st = sc.nextLine();
			String[] stArr = st.split(" ");

			for (int j = 0; j < n; j++) {
				int a = Integer.parseInt(stArr[j]);

				if (a == 1) { 
					graph.get(i).add(j); //방향그래프*****(양반향 아님!!!)
				}
			}
		}
		
		for(int i=0; i<n; i++) { //인덱스 0부터 시작 주의*****
			for(int j=0; j<n; j++) {
				visited = new boolean[n]; //새롭게 초기화
				
				dfs(i, j); //해당 값부터 dfs 반복
				
				if(flag == true) { //목표까지 도달가능하면 +1
					result[i][j] = 1;
					flag = false; //초기화
				}
			}
		}

		for(int i=0; i<n; i++) { //출력
			for(int j=0; j<n; j++) {
				System.out.print(result[i][j] + " ");
			}
			System.out.println();
		}
	}

}