[자바] 백준 1260 - DFS와 BFS

DFS와 BFS에 대한 기본적인 개념을 되짚어볼 수 있는 문제라 알고리즘 공부 시작할 때마다 다시 풀어보게 된다.

이번에 푼 코드는 아래와 같다.

 import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

public class Main1260_DFS와BFS {

	static int N;
	static int M;
	static int start;
	static Node[] graph;
	static boolean[] visited;
	static StringBuilder sb;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().trim().split(" ");
		
		N = Integer.parseInt(str[0]);
		M = Integer.parseInt(str[1]);
		start = Integer.parseInt(str[2]);
		graph = new Node[N+1];
		visited = new boolean[N+1];
		sb = new StringBuilder();
		
		for(int n=1;n<=N;n++) {
			graph[n] = new Node(n, new ArrayList<Integer>());
		}
		
		int first=0, second=0;
		for(int m=1;m<=M;m++) {
			str = br.readLine().trim().split(" ");
			first = Integer.parseInt(str[0]);
			second = Integer.parseInt(str[1]);
			
			graph[first].link.add(second);
			graph[second].link.add(first);
		}
		
		for(int i=1;i<=N;i++) {
			Collections.sort(graph[i].link);
		}
		
		dfs(start);
		sb.toString().trim();
		sb.append("\n");
		
		visited = new boolean[N+1];
		bfs();
		
		System.out.println(sb.toString());

	}
	
	private static void bfs() {
		visited[start] = true;
		sb.append(start+" ");
		
		Queue<Integer> que = new LinkedList<Integer>();
		que.offer(start);
		
		int tmp;
		ArrayList<Integer> list;
		while(!que.isEmpty()) {
			tmp = que.poll();
			
			list = graph[tmp].link;
			for (Integer i : list) {
				if(!visited[i]) {
					visited[i] = true;
					sb.append(i+" ");
					que.offer(i);
				}
			}
		}
	}

	//일단 방문하기만 하면 끝. 
	//모든 경우의 수를 찾을 필요가 없으므로 visited[start]을 원복시켜놓지 않는다. 
	private static void dfs(int start) {
		visited[start] = true;
		sb.append(start+" ");
		
		ArrayList<Integer> list = graph[start].link;
		for (Integer i : list) {
			if(!visited[i]) {
				dfs(i);
			}
		}
	}

	static class Node{
		int nodeNum;
		ArrayList<Integer> link;
		
		public Node() {
			
		}
		
		public Node(int nodeNum, ArrayList<Integer> link) {
			this.nodeNum = nodeNum;
			this.link = link;
		}
	}
}

굳이 Node Class를 만들 필요는 없었는데 ArrayList의 배열을 어떻게 만들어야 할지 모르겠어서 Node Class를 만들었다.

근데 이전에 푼 코드를 보니까 ArrayList의 배열을 만들어놨는데, 지금봐도 이해가 잘 안 가는거 보니까 그냥 외워서 만들었나보다.

 ArrayList<Integer>[] adList = adList = (ArrayList<Integer>[]) new ArrayList[N+1];