Algorithm, boj, 1260(DFS와 BFS)

• ##DFS
• 깊이 우선 탐색
• 재귀 함수로 풀이

• BFS

• 넓이 우선 탐색
• 큐로 풀이

package org.baekjoon;


import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class test1260_1 {

	static boolean[] visited;
	static ArrayList<Integer>[] list;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int node = sc.nextInt();	// 노드 개수
		int line = sc.nextInt();	// 간선 개수
		int start = sc.nextInt();		// 시작 노드

		// 노드 개수 만큼 인접리스트을 만들어준다. 인덱스 헷갈림을 방지하기 위해 +1 해준다.
		list = new ArrayList[node+1];
		// 인접리스트 초기화
		for (int i=1; i< node+1; i++)
			list[i] = new ArrayList<Integer>();

		// 간선 개수만큼 입력이 들어 온다.
		for (int i=0; i < line; i++) {
			 int x = sc.nextInt();
			 int y = sc.nextInt();

			 // 자신의 노드에서 갈 수 있는 노드를 추가해준다.
			 list[x].add(y);
			 list[y].add(x);
		}

		// 인접한 노드가 두개 이상일때 작은 숫자부터 방문 하므로, 오름차순으로 정렬 해준다.
		for (int i=1; i<node+1; i++)
			Collections.sort(list[i]);

		// 노드의 방문 여부를 표시하는 배열. false로 초기화 해준다. 인덱스 혼동 방지를 위해 node+1 해준다.
		visited = new boolean[node+1];
		dfs(start);
		System.out.println();

		// 노드 방문 여부 표시 배열 초기화
		visited = new boolean[node+1];
		bfs(start);

		sc.close();
	}

	static void bfs(int start) {
		// bfs는 큐로 해결.
		Queue<Integer> qu = new LinkedList<Integer>();

		// 첫번째 노드를 방문한다.
		qu.add(start);
		visited[start] = true;

		// 큐메 넣고(방문) 빼면서 , 큐가 빌때까지 반복한다.
		while (!qu.isEmpty()) {
				// 큐에서 노드 한개를 뺀다.
				int out = qu.poll();
				System.out.print(out+ " ");
				// 빼낸 노드의 인접 노드를 방문
				for (int x : list[out]) {
					// 인접노드를 방문한적이 없으면 방문표시 후, 큐에 삽입
					if(visited[x] == false) {
						visited[x] = true;
						qu.add(x);
					}
				}


		}
	}

	static void dfs(int start) {

		// 방문했으면 함수 종료
		if (visited[start] == true)
			return;

		// 방문표시
		visited[start] = true;
		System.out.print(start+" ");

		// 방문한 노드와 인접한 노드를 방문한다.
		for (int i : list[start]) {
			// 인접노드를 방문안했으면 방문하러 간다.
			if (visited[i] == false)
				dfs(i);
		}
	}

}

---

Reference

문제로 가기 문제 풀이 참고