[이코테] P2 주요 알고리즘과 실전 문제: DFS/BFS

💡 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘

DFS

DFS(Depth-First Search) 알고리즘은 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 이 알고리즘은 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. (또한 일반적으로 인접한 노드 중에서 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순서부터 처리한다.)
4. 2.의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

bool visited[101];
vector<int> graph[101];

void dfs(int start)
{
	visited[start] = true;

	for (int i = 0; i < graph[start].size(); i++)
	{
		int next = graph[start][i];

		if (!visited[next])
		{
			dfs(next);
		}
	}
}

BFS

BFS(Breadth-First Search) 알고리즘은 너비 우선 탐색이라는 의미를 가진다. 가까운 노드부터 탐색하는 알고리즘이다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어 가까운 노드부터 탐색을 진행하게 된다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. (마찬가지로 인접한 노드가 여러 개 있을 때, 숫자가 작은 노드부터 먼저 큐에 삽입한다고 가정한다.)
4. 2.의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

bool visited[101];
vector<int> graph[101];

void bfs(int start)
{
	queue<int> q;
	q.push(start);
	visited[start] = true;

	while (!q.empty())
	{
		int current = q.front();
		q.pop();

		for (int i = 0; i < graph[current].size(); i++)
		{
			int next = graph[current][i];
			if (!visited[next])
			{
				q.push(next);
				visited[next] = true;
			}
		}
	}
}

	DFS	BFS
동작 원리	스택	큐
구현 방법	재귀 함수 이용	큐 자료구조 이용

---

음료수 얼려 먹기

• 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시
• 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.

입력 조건

• 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. $(1 ≤ N, M ≤ 1,000)$
• 두 번째 줄부터 N + 1번째 줄까지 얼음 틀의 형태가 주어진다.
• 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.

출력 조건

• 한 번에 만들 수 있는 아이스크림의 개수를 출력한다.

입력 예시 1

4 5
00110
00011
11111
00000

출력 예시 1

3

입력 예시 2

15 14
00000111100000
11111101111110
11011101101110
11011101100000
11011111111111
11011111111100
11000000011111
01111111111111
00000000011111
01111111111000
00011111111000
00000001111000
11111111110011
11100011111111
11100011111111

출력 예시 2

8

📝풀이

// dfs.cpp
#include <iostream>
#include <vector>
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int map[1001][1001];
bool visited[1001][1001];
int N, M;
int cnt = 0;

using namespace std;

void dfs(int x, int y)
{
    visited[x][y] = true;

    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
        if (!visited[nx][ny])
        {
            if (map[x][y] != map[nx][ny]) continue;
            dfs(nx, ny);
            visited[nx][ny] = true;
        }
    }
}

void main()
{
    cin >> N >> M;

    for (int i = 0; i < N; i++)
    {
        string str;
        cin >> str;
        for (int j = 0; j < M; j++)
        {
            map[i][j] = str[j] - '0';
        }
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (!visited[i][j] && map[i][j] == 0)
            {
                dfs(i, j);
                cnt++;
            }
        }
    }

    cout << cnt;
}

미로 탈출

• 동빈이의 위치 (1, 1), 미로의 출구 (N, M)에 위치
• 괴물이 있는 부분은 0, 괴물이 없는 부분은 1로 표시
• 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수

입력 조건

• 첫째 줄에 두 정수 N, M$(4 ≤ N, M ≤ 200)$이 주어집니다. 다음 N개의 줄에는 각각 M개의 정수(0 혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이 붙어서 입력으로 제시된다. 또한 시작 칸 과 마지막 칸은 항상 1이다.

출력 조건

• 첫째 줄에 최소 이동 칸의 개수를 출력한다.

입력 예시

5 6 
101010 
111111 
000001 
111111 
111111

출력 예시

10

📝풀이

#include <iostream>
#include <queue>
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int map[201][201];
int N, M;
int cnt = 0;

using namespace std;

void bfs(int x, int y)
{
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
        if (map[nx][ny] == 0) continue; // 있어도 그만 없어도 그만
        if (map[nx][ny] <= map[x][y])
            map[nx][ny] = map[x][y] + 1;
    }
}

void main()
{
    cin >> N >> M;

    for (int i = 0; i < N; i++)
    {
        string str;
        cin >> str;
        for (int j = 0; j < M; j++)
        {
            map[i][j] = str[j] - '0';
        }
    }

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            bfs(i, j); // bfs가 아니긴 함;;
            // queue를 써서 처음 방문한 경우에만 bfs 돌게 만들기.. 시간초과 유의
        }
    }

    cout << map[N-1][M-1];
}