Take it easy

최소한 의 지렁이로, 최대한 많은 효율을 내고 싶은 문제이다.

지렁이들이 "연결"된 곳을 다닐 수 있다

나는 여기서 해당 문제는 DFS 와 BFS를 이용할 수 있을 거라고 생각 했다.

이렇게 색칠한 음영별로 깊이있게 탐색을 하든, 넓게 탐색을 하든 다 찾아내면되는 것이다.

DFS 코드로 나타내면 이렇다.

#include<iostream>
using namespace std;

int map[50][50];
int n, m,k;

int direct[4][2] = {{-1,0},{0,-1},{1,0},{0,1}};

void dfs(int i, int j)
{
    map[i][j] = 0;
    for(int k=0;k<4;k++)
    {
        int x = i+direct[k][0];
        int y = j+direct[k][1];
        if(x>= 0 && x < m && y >=0 && y <n)
        {
            if(map[x][y] == 1)
            {
                dfs(x,y);
            }
        }
    }
}

int main() {
    int tnum;
    cin >> tnum;

    for(int tcase = 0; tcase<tnum;tcase++)
    {
	    int result=0;
        cin >> m >> n>>k;

        for (int i = 0; i < k; i++)
        {
            int t1, t2;
            cin >> t1 >> t2;
            map[t1][t2] = 1;
        }

        for (int i = 0; i <m; i++)
        {
            for(int j=0;j<n;j++)
            {
                if(map[i][j]==1)
                {
                    dfs(i,j);
                    result++;
                }
            }
        }
        cout << result << "\n";

    }
	

}

BFS 코드는 다음과 같다.

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

int map[50][50];
int n, m,k;

struct point
{
    int x;
    int y;
};
queue<point> q;

void bfs(int i, int j)
{
    if(map[i][j]==0) return;
    map[i][j] = 0;

    for(int k=0;k<4;k++)
    {
        int x = i+direct[k][0];
        int y = j+direct[k][1];
        if(x>= 0 && x < m && y >=0 && y <n)
        {
            if(map[x][y] == 1)
            {
                point p ;
                p.x = x;
                p.y = y;
                q.push(p);
            }
        }
    }
}
int main() {
    int tnum;
    cin >> tnum;

    for(int tcase = 0; tcase<tnum;tcase++)
    {
	    int result=0;
        cin >> m >> n>>k;

        for (int i = 0; i < k; i++)
        {
            int t1, t2;
            cin >> t1 >> t2;
            map[t1][t2] = 1;
        }

        for (int i = 0; i <m; i++)
        {
            for(int j=0;j<n;j++)
            {
                if(map[i][j]==1)
                {
                    point p;
                    p.x = i;
                    p.y = j;

                    q.push(p);
                    while(!q.empty())
                    {
                        int t1,t2;
                        p = q.front();
                        t1 = p.x;
                        t2 = p.y;
                        q.pop();

                        bfs(t1,t2);
                    }
                    result++;
                }
            }
        }
        cout << result << "\n";

    }
	

}

나는 이런 문제에 대해서는 DFS가 상대적으로 직관적이고 좋은 것 같다. 

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