[알고리즘] DFS & BFS

그래프 탐색 알고리즘 : DFS/BFS

• 탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• 대표적인 그래프 탐색 알거리즘은 DFS와 BFS가 있음

Stack

• LIFO (Last In First Out)
• 입구와 출구가 동일

import java.util.*;
...
Stack<Integer> s = new Stack<>();
s.push(5); // 삽입
s.push(2);
s.pop(); // 삭제

Queue

• FIFO (First In First Out)
• 입구와 출구가 다름

import java.util.*;
...
Queue<Integer> q = new LinkedList<>();
q.offer(5); // 삽입
q.offer(3);
q.poll(); // 삭제

Recursive Function (재귀함수)

• 자기 자신을 다시 호출하는 함수
• 재귀 함수를 문제 풀이에 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야됨
• 종료 조건을 명시하지 않으면 함수가 무한히 호출될 수 있음

void recu(int i) {
    if (i>=100)
        return;
    System.out.println('재귀 함수 호출');
    recu(++i);
}

재귀함수 활용 - 최대공약수 계산 (유클리드 호제법)

void gcd(int a, int b) {
    if (a % b == 0)
        return b;
    else {
    	return gcd(b, a%b);
    }
}

DFS (Depth-First Search)

• 깊이 우선 탐색
• 스택 또는 재귀 함수를 이용
• 예제 코드

BFS (Breadth-First Search)

• 너비 우선 탐색, 가까운 노드부터 우선적으로 탐색
• 큐를 이용
• 예제 코드

문제 1: 음료수 얼려 먹기

N * M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시한다.
구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.
이 때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.
[입력 예]
4 5
00110
00011
11111
00000
[출력 예]
3

해답

문제 2: 미로 탈출

희동이는 N*M 크기의 직사각형 형태의 미로에 갇혔다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다.
희동이의 위치는 (1, 1)이며 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다.
이 때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시된다.
미로는 반드시 탈출할 수 있는 형태로 제시된다
이 때 희동이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오.
칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.
[입력 예]
5 6
101010
111111
000001
111111
111111
[출력 예]
10

해답

자료 출처 : 이것이 취업을 위한 코딩 테스트다, 나동빈