Algorithm, boj, 12403(경로찾기)

• DFS

  풀이

• 좌표를 입력받아 서로 연결된 간선의 정보를 list 배열에 넣는다.
• list배열의 내용을 dfs로 확인하며 확인된 노드는 result에 넣는다.

package org.baekjoon;

import java.util.*;
public class test11403 {

	static ArrayList<Integer>[] list;  // 입력받은 좌표의 간선
  static boolean[] visited;          // 방문여부 화인 배열
	static int[][] result;             // 출력 내용의 좌표가 들어간다
	static int stage;
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		int size = sc.nextInt();

		result = new int[size][size];
		list = new ArrayList[size];
		for (int i=0; i<size; i++) {
			list[i] = new ArrayList<Integer>();
		}

		for (int i=0; i<size; i++) {
			for (int j=0; j<size; j++) {
				if (sc.nextInt() == 1) {
					list[i].add(j);
				}
			}
		}

		 for(stage=0; stage<size; stage++) {
			visited = new boolean[size];
			dfs(stage);
		}

		 for(int i=0; i<size; i++) {
			 for(int e:result[i])
				 System.out.print(e+" ");

			 System.out.println();
		 }


	}
	static void dfs(int node) {

		if (list[node].isEmpty())
			return;

		for (int e:list[node]) {
			if (visited[e] == false) {
				visited[e] = true;
				result[stage][e] = 1;
				dfs(e);
			}
		}

	}

}

---

Reference

문제로 가기