백준 1260; Java

import java.util.*;
import java.io.*;

public class Main {
	static int N, M, V;
	static ArrayList<ArrayList<Integer>> graph;
	static boolean[] visited;
	static ArrayList<Integer> List;
	
	public static void dfs(int s) {
		visited[s]=true;
		List.add(s);
		for(int i:graph.get(s)) {
			if(!visited[i]) {
				dfs(i);
			}
		}
	}
	
	public static void bfs(int s) {
		Queue<Integer> q=new LinkedList<>();	//탐색해 볼 정점을 넣음 
		q.add(s);
		visited[s]=true;
		List.add(s);
		while(!q.isEmpty()) {
			int cur=(int) q.poll();
			for(int i:graph.get(cur)) {
				if(!visited[i]) {
					q.offer(i);
					visited[i]=true;
					List.add(i);
				}
			}
		}
	}
	
	public static void main(String[] args)throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String str[]=br.readLine().split(" ");
		N=Integer.parseInt(str[0]);
		M=Integer.parseInt(str[1]);
		V=Integer.parseInt(str[2])-1;
		
		int v1, v2;
		graph=new ArrayList<ArrayList<Integer>>(N);
		for(int i=0;i<N;i++) {
			graph.add(new ArrayList<>());
		}
		
		for(int i=0;i<M;i++) {
			str=br.readLine().split(" ");
			v1=Integer.parseInt(str[0])-1;
			v2=Integer.parseInt(str[1])-1;
			
			graph.get(v1).add(v2);
			graph.get(v2).add(v1);
		}
	
		visited=new boolean[N];
		List=new ArrayList<Integer>();
		
		for (int i = 0; i < N; i++) { Collections.sort(graph.get(i)); }

		dfs(V);
		for(int i:List) {
			System.out.print((i+1)+" ");
		}
		System.out.println();
		
		Arrays.fill(visited, false);
		List.clear();
		
		bfs(V);
		for(int i:List) {
			System.out.print((i+1)+" ");
		}
	}
}

 

- DFS

procedure dfs(G: connected graph with vertices v1, v2,...,vn)
	T:= tree consisting a vertex v1
	visit(v1)
    
procedure visit(v: vertex of G)
	for each vertex w adjacent to v
		if w is not in T then 
			add vertex w and edge {v, w} to T
			visit(w)

 

- BFS

procedure bfs(G: connected graph with vertices v1, v2, ..., vn)
	T:= tree consisting a vertex v1
	L:= empty list
	put v1 in L, which is a list of unprocessed vertices
   
    while L is not empty
    	remove the first vertex v from L
        for each vertex w adjacent to v
        	if x is not in L and not in T then
            	add w in L
                add w, edge {v, w} in T

 

 

---

처음에는 graph를 ArrayList<PriorityQueue<Integer>>로 생각해서 문제를 풀었다.

예를 들자면 정점 3의 인접 정점 리스트 즉, graph.get(3)를 PriorityQueue로 두면 굳이 정렬해주지 않아도 인접 정점들이 오름차순으로 저장될 줄 알았다. 근데 계속 틀려서.. 걍 arraylist로 하고 정렬돌렸다. 우선순위 큐 사용이 아직 미숙한가보다..