알고리즘 유형별 문제를 모아 그 사이의 일관된 공통점을 찾아보려고 한다. 매번 알고리즘 공부해야지 하고 마음먹었다가 시간이 지나면 까먹고 다시 원점으로 돌아오게 되는데, 역시 정리를 하지 않아서 그런 것 같다. 문과생이었어서 그런지 유형별 학습이 더 익숙하다. C++을 기준으로 정리할 예정이다.

DFS

https://www.acmicpc.net/problem/2667

한 맵에서 dfs를 여러번 해야 하는 문제이다.

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int mapState[30][30] = {0};
int n;
vector<int> cnt(900);

int idx = 0;

//dfs
void solve(int x, int y)
{
    if (x >= n || x < 0 || y >= n || y < 0)
        return;
    if (mapState[y][x] != 1)
        return;
    mapState[y][x] = 2;
    cnt[idx]++;

    int nx[4] = {0, -1, 1, 0};
    int ny[4] = {-1, 0, 0, 1};

    for (int i = 0; i < 4; i++)
    {
        solve(x + nx[i], y + ny[i]);
    }
}

int main()
{
	//입력받기
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%1d", &mapState[i][j]);
        }
    }

  	//dfs여러번 돌리기
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (mapState[i][j] == 1)
            {
                solve(j, i);
                idx++;
            }
        }
    }

    sort(cnt.begin(), cnt.begin() + idx);

    cout << idx << endl;
    for (int i = 0; i < idx; i++)
        cout << cnt[i] << endl;
}

여기서 dfs는 세 부분으로 나뉜다.

void solve(int x, int y)
{
  	//1. 범위 안에 있는지 확인, 방문했는지 확인
    if (x >= n || x < 0 || y >= n || y < 0)
        return;
    if (mapState[y][x] != 1)
        return;
  	
  	//2. 방문 체크
    mapState[y][x] = 2;
    cnt[idx]++;

  
  	//3. 상하좌우로 이동
    int nx[4] = {0, -1, 1, 0};
    int ny[4] = {-1, 0, 0, 1};

    for (int i = 0; i < 4; i++)
    {
        solve(x + nx[i], y + ny[i]);
    }
}

이것이 기본적인 dfs의 틀이다. 범위 안이나 조건 확인은 상하좌우로 이동하기 전에 확인하여도 된다.(즉 solve 전에 체크해도 된다.)

1번이 존재하지 않으면 과도한 함수호출로 시간초과에 빠지거나 잘못된 곳에 접근해서 런타임 에러가 발생하게 된다.

참고

https://m.blog.naver.com/PostView.nhn?blogId=kimmy5000&logNo=220718380275&proxyReferer=https%3A%2F%2Fwww.google.com%2F
이런 문제도 존재한다.