백준 10026 적록색약(dfs)

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

10026번: 적록색약

#include <iostream>

using namespace std;
const int MAX = 100;
int N;
string graph[MAX];
bool visited[MAX][MAX];
int cnt;
typedef struct
{
    int x, y;
} Dir;
Dir Dirmove[4] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

void dfs(int x, int y)
{

    visited[x][y] = true;
    for (int i = 0; i < 4; i++)
    {
        int nextX = x + Dirmove[i].x;
        int nextY = y + Dirmove[i].y;
        if (0 <= nextX && nextX < N && 0 <= nextY && nextY < N && graph[x][y] == graph[nextX][nextY] && !visited[nextX][nextY])
            dfs(nextX, nextY);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> graph[i];
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (!visited[i][j])
            {
                cnt++;
                dfs(i, j);
            }
        }
    }
    cout << cnt;
    cnt = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            visited[i][j] = false;
            if (graph[i][j] == 'G')
                graph[i][j] = 'R';
        }
    }

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (!visited[i][j])
            {
                cnt++;
                dfs(i, j);
            }
        }
    }
    cout << " " << cnt;
}

 

이 문제 또한 전형적인 dfs 모양으로 풀었다.

visited를 초기화 시킬 때 graph 배열 자체를 수정해서 dfs 함수를 간단한 형태로 유지될 수 있게 설계했다.