[코딩테스트] 백준 1260 DFS와 BFS

📌 문제

• 그래프를 DFS & BFS로 탐색한 결과를 출력하는 프로그램을 작성
• 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료
• 정점 번호는 1번부터 N번까지이다.

📌 나의 생각

문제를 해결 후, 다른 사람들의 코드 작성을 보니 대체로 배열로 접근해서 문제를 풀었다.
노드가 많은 경우와 정리하기 쉬운 ArrayList를 사용해 문제를 해결해 봤다.

자꾸 ArrayList를 iterator로 접근해서 요소를 가져오려 하는 습관을 버릴 것
forEach문이 보기에도 편하고 접근하기 편리함.

📌 DFS

⬇️ DFS 코드

public static void DFS(int L,int k,int n) {
		if(L==n) {
			return;
		}else {
			//k부터 시작
			if(ch[k]==0) {
				ch[k]=1;
				System.out.print(k+" ");
				for(int x : list.get(k)) {
					if(ch[x]==0) {
						DFS(L+1,x,n);
					}
				}
			}
		}
	}

📌 BFS

⬇️ BFS 코드

public static void BFS(int k) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(k);
		ch[k]=1;
		System.out.print(k+" ");
		while(!q.isEmpty()) {
			ArrayList<Integer> tmp = list.get(q.poll());
			for(int node:tmp) {
				if(ch[node]==0) {
					q.offer(node);
					System.out.print(node+" ");
					ch[node]=1;
				}
			}
		}
	}

⬇️ 내가 작성한 전체 코드

package baekjoon;
import java.util.*;
public class DFS_and_BFS {
	static int[] ch;
	static ArrayList<ArrayList<Integer>> list;
	public static void DFS(int L,int k,int n) {
		if(L==n) {
			return;
		}else {
			//k부터 시작
			if(ch[k]==0) {
				ch[k]=1;
				System.out.print(k+" ");
				for(int x : list.get(k)) {
					if(ch[x]==0) {
						DFS(L+1,x,n);
					}
				}
			}
		}
	}
	public static void BFS(int k) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(k);
		ch[k]=1;
		System.out.print(k+" ");
		while(!q.isEmpty()) {
			ArrayList<Integer> tmp = list.get(q.poll());
			for(int node:tmp) {
				if(ch[node]==0) {
					q.offer(node);
					System.out.print(node+" ");
					ch[node]=1;
				}
			}
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//n개의 노드 m개의 간선 k부터 탐색 시작
		int n = sc.nextInt();
		int m = sc.nextInt();
		int k = sc.nextInt();
		ch = new int[n+1];
		list = new ArrayList<>();
		for(int i=0;i<=n;i++) {
			list.add(new ArrayList<>());
		}
		for(int i=0;i<m;i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			list.get(a).add(b);
			list.get(b).add(a);
		}
		for(int i=1;i<=n;i++) {
			Collections.sort(list.get(i));
		}
		DFS(0, k, n);
		System.out.println();
		ch = new int[n+1];
		BFS(k);
	}

}