알고리즘 유형3. DFS, BFS feat. 유레카

DFS, BFS

그래프, tree를 어떻게 자료구조로 표현할것인가?

 

를 알기 위해 먼저 자료구조 Stack, Queue를 먼저 알아봤다.

Java Platform SE 8

Stack : FILO or LIFO 불공평한 자료구조 입구 1개 (입구와 출구가 같다)

• push(n) : n을 스택에 입력 / pop() : 맨 위(앞)에 있는 원소 반환 + 삭제 / peek() : 맨 위(앞)에 있는 원소 반환
• Stack의 자료구조는 stack, queue, arraydeque로 만들 수 있다. (하지만 왠만하면 arraydeque를 이용)

 

Queue : FIFO 입구 1개, 출구 1개, 같은 방향으로 요소들이 흐른?다

• offer(n) : 큐 끝에 n 추가 / poll() : 큐 앞에 요소 반환 + 제거 / peek() : 큐 앞에 있는 요소 반환
• Queue의 자료구조는 LinkedList, ArrayDeque, PriorityQueue(내부는 heap구조) 로 만들 수 있다.

package DFSBFS_ch05;

import java.util.Arrays;
import java.util.PriorityQueue;

// PriorityQueue (우선 순위 - 정렬된 결과를 추출, 내부는 heap 구조) 연습
public class 큐4 {

	public static void main(String[] args) {
		{
			// Integer
			PriorityQueue<Integer> pqueue = new PriorityQueue<>();
			pqueue.offer(3);
			pqueue.offer(2);
			pqueue.offer(7);
			pqueue.offer(5);
			pqueue.offer(9);
			
			while ( ! pqueue.isEmpty()) {
				System.out.println(pqueue.poll());
			}
			
			for (Integer i : pqueue) {
				System.out.println(i);	// 2 3 7 5 9 정렬 안됨, 입력순도 아님
			}
		}

		{
			// String
			PriorityQueue<String> pqueue = new PriorityQueue<>();
			pqueue.offer("b3");
			pqueue.offer("a2");
			pqueue.offer("x7");
			pqueue.offer("d5");
			pqueue.offer("s9");
			
			while ( ! pqueue.isEmpty()) {
				System.out.println(pqueue.poll());
			}
		}
		
		{
			// user defined class
			// 정렬 조건 추가 3: class에 comparable, anonymous 객체, lambda
			PriorityQueue<Node> pqueue = new PriorityQueue<>();
			pqueue.offer(new Node(3, 5, 2));
			pqueue.offer(new Node(7, 1, 4));
			pqueue.offer(new Node(5, 2, 9));
			pqueue.offer(new Node(1, 1, 5));
			
			while ( ! pqueue.isEmpty()) {
				System.out.println(pqueue.poll());
			}
		}
		
		{
			// user defined class + lambda
			// 이럴 경우, class에 Implements 안붙여도됌.
			PriorityQueue<Node> pqueue = new PriorityQueue<>((n1, n2) -> n1.y - n2.y);
			pqueue.offer(new Node(3, 5, 2));
			pqueue.offer(new Node(7, 1, 4));
			pqueue.offer(new Node(5, 2, 9));
			pqueue.offer(new Node(1, 1, 5));
			
			while ( ! pqueue.isEmpty()) {
				System.out.println(pqueue.poll());
			}
		}
		
		{
            // user defined class + lambda
            // 정렬 조건 추가 3: class 에 Comparable, anonymous 객체, lambda
            PriorityQueue<int[]> pqueue = new PriorityQueue<>( (a1, a2) -> a1[2] - a2[2] );
            pqueue.offer(new int[] {3, 5, 2});
            pqueue.offer(new int[] {7, 1, 4});
            pqueue.offer(new int[] {5, 2, 9});
            pqueue.offer(new int[] {3, 1, 5});
            
            while( ! pqueue.isEmpty() ) {
                System.out.println(Arrays.toString(pqueue.poll()));
            }
        }       

	}

	static class Node implements Comparable<Node>{
		int y, x, c;
		Node(int y, int x, int c){
			this.y = y;
			this.x = x;
			this.c = c;
		}
		@Override
		public String toString() {
			return "[y=" + y + ", x=" + x + ", c=" + c + "]";
		}
		@Override
		public int compareTo(Node o) {
//			return this.y - o.y;	// y 기준 오름차순 
//			return o.y - this.y;	// y 기준 내림차순
//			return this.c - o.c;	// c 기준 오름차순
			return this.y == o.y ? this.x - o.x : this.y - o.y;	// y가 같을 경우 x값에 따라 오름차순
		}
	}

		
}

 

1. 인접 행렬 (matrix) : (노드)정점 중심

• 정점 / 정점 + 비용 / 정점 + 비용 + 방향
• 인접행렬은 간선이 적을수록 메모리 낭비가 심함

2. 인접 리스트 : (노드)정점 중심

• arraylist of arraylist
• 정점 / 정점 + 비용 / 정점 + 비용 + 방향
• 인접 리스트는 정점 수 대비 간선 수가 매우 많을 때 메모리 낭비가 심함

주의! 인접행렬이라고 무조건 메모리 낭비가 심하다! 라고 말하면 안됌

 

3. 간선 리스트 : 간선 중심

정점&간선

[자료구조] 그래프를 저장하는 방법 3가지 : 인접 행렬, 인접 리스트, 간선 리스트 with Python

 

	DFS	BFS
동작 원리	Stack	Queue
구현 방법	재귀함수 이용	Queue 자료구조 이용
예시		최단경로

 

 

추가 문제 : 백준 1260

:  DFS와 BFS를 출력하는 문제, 양방향 그래프와 오름차순으로 정렬하는 부분에서 막혔었음
https://www.acmicpc.net/problem/1260

 

package DFSBFS_ch05;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class BaekJoon_1260 {
	static int N, M, V;
	static List<List<Integer>> adjList = new ArrayList<>(); 
	static boolean[] visit;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader (new InputStreamReader (System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		V = Integer.parseInt(st.nextToken());
		
		// 자료구조
        for (int i = 0; i < N+1; i++) {
            adjList.add(new ArrayList<Integer>());
        }
		
		for (int n = 0; n < M; n++) {
			st = new StringTokenizer(br.readLine());
			int i = Integer.parseInt(st.nextToken());
			int j = Integer.parseInt(st.nextToken());
			
			adjList.get(i).add(j);
			adjList.get(j).add(i);	// 양방향 그래프이므로 반대쪽도 추가
		}
		
		// 오름차순으로 정렬
		for (List<Integer> list : adjList) {
            Collections.sort(list);
        }
		
		visit = new boolean[N+1];
		dfs(V);
		System.out.println();
		
		visit = new boolean[N+1];
		bfs(V);
	}
	
	static void dfs(int V) {
		visit[V] = true;
		
		System.out.print(V + " ");
		
		List<Integer> list = adjList.get(V);
		for (Integer i : list) {
			if (visit[i]) continue;
			dfs(i);
		}
	}
	
	
	static void bfs(int V) {
		Queue<Integer> queue = new ArrayDeque<>();
		queue.offer(V);
		visit[V] = true;
		
		while(! queue.isEmpty() ) {
            int v = queue.poll();
            
            System.out.print(v + " ");
            
            List<Integer> list = adjList.get(v);
            for (Integer i : list) {
                if( visit[i]) continue;
                queue.offer(i);
                visit[i] = true;
            }
        }
		
	}
}