BOJ 1260 DFS와 BFS

단순히 DFS와 BFS를 구현하는 문제이다.

근데 이 문제의 핵심은 " 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고," 이다.

이를 간단히 하기 위해서는 인접행렬로 그래프를 구현하면 된다 . 인접행렬로 그래프를 구현하고, 간선을 탐색할 경우 당연히 인덱스 차례대로 방문하기 때문에 "정점번호가 작은 것을 먼저 방문하고"가 자연스럽게 충족된다.

반면에 인접리스트로 구현할 경우, 간선 노드들이 정렬이 되어있지 않으므로 정렬을 해주어야 한다.

나는 인접 리스트 버전과 인접 행렬버전 모두를 구현했다. 

먼저 인접행렬버전을 보자.

 

 

인접행렬은 당연히 (n+1)*(n+1) 의 크기로 구현을 해주고, BFS를 위해 큐도 구현해주어야 한다. 또한 visited 배열 (방문을 표시하는 배열) 은 dfs가 끝난후 초기화 해주어야 한다.

1. DFS와 BFS 자바 소스 (인접행렬 사용)

import java.util.LinkedList;
import java.util.Queue;
import java.util.Arrays;

import java.util.*;

public class Main {
	static int v,e,n;
	static boolean[]visited; //방문표시 
	static int graph[][]; //인접행렬
	static Queue<Integer> que; //BFS를 위한 큐 
	
	public static void dfs(int v) {
		visited[v]=true;
		System.out.print(v + " ");
		for(int i=0; i<n+1;i++) {
			if(graph[v][i]==1 && !visited[i])
				dfs(i);
		}
	}
	
	public static void bfs(int v) {
		que.offer(v);
		int tmp;
		visited[v]=true;
		while(!que.isEmpty()) {
			tmp =que.peek();
			que.poll();
			System.out.print(tmp+" ");
			for(int i=0; i<n+1; i++) {
				if(graph[tmp][i]==1 && !visited[i]) {
					que.offer(i);
					visited[i]=true;
				}
			}
			
		}
	}
	
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		n=sc.nextInt(); //정점 수
		e=sc.nextInt(); //간선 수
		v=sc.nextInt(); // 출발 노드
		visited=new boolean[n+1]; 
		graph=new int[n+1][n+1]; //그래프생성 
		que = new LinkedList<>(); //큐 생성 
		for(int i=0; i<e; i++) { //간선 입력 
			int t= sc.nextInt();
			int f= sc.nextInt();
			graph[t][f]=graph[f][t]=1;
		}
		dfs(v);
		Arrays.fill(visited,false); //visited 배열 초기화 
		System.out.println();
		bfs(v);
	}
}

 

다음은 인접 리스트 사용버전이다.

다른건 다 똑같지만, 인접리스트는 ArrayList로 구현 되었고, 간선이 모두 입력되면, ArrayList를 오름차순으로 정렬해준 후 dfs와 bfs를 실행하였다.

 

2. DFS와 BFS 자바소스 (인접리스트 이용)

import java.util.LinkedList;
import java.util.Queue;
import java.util.Comparator;
import java.util.*;
import java.util.Collections;

public class Main {
	static int v,e,n;
	static boolean[]visited;
	static ArrayList<ArrayList<Integer>> list;
	static Queue<Integer> que;
	
	public static void dfs(int start) {
		visited[start]=true;
		System.out.print(start+" ");
		for(int i: list.get(start)) {
			if(!visited[i])
				dfs(i);
		}
	}
	
	public static void bfs(int start) {
		visited[start]=true;
		que.offer(start);
		int tmp;
		while(!que.isEmpty()) {
			tmp=que.peek();
			System.out.print(tmp +" ");
			que.poll();
			for(int i: list.get(tmp)) {
				if(!visited[i]) {
					que.offer(i);
					visited[i]=true;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt(); //노드 개수
		e = in.nextInt(); // 간선 개수
		v = in.nextInt(); //시작 정점 
		list = new ArrayList<>(); //리스트 생성
		que=new LinkedList<>(); //큐 생성 
		visited= new boolean[n+1]; 
		for(int i=0; i<=v ; i++) //리스트 초기화 
			list.add(new ArrayList<>());
		
		for(int i=0; i<e ;i++) { //간선 입력 
			int t = in.nextInt();
			int f = in.nextInt();
			list.get(t).add(f);
			list.get(f).add(t);
		}
		
		for(int i=0; i<n; i++) { //오름차순 정렬 
			Collections.sort(list.get(i), new Ascending());}
		
		dfs(v);
		System.out.println();
		Arrays.fill(visited, false); //vistied 배열 초기화 
		bfs(v);
		in.close();
	}
}


class Ascending implements Comparator<Integer>{
	public int compare(Integer a, Integer b) {
		return a.compareTo(b);
	}
}

 

 

두 방법의 속도차이는 거의 없었지만 , 메모리는 예상대로 인접리스트를 사용하는 편이 더 작았다