BOJ 9337 Flood-It

사용한 알고리즘

완전탐색, DFS

알고리즘 설명

Flood-It 게임을 몰라서 조건을 해깔려 많이 해메었다.
문제는 단순한 완전탐색이다.
0,0 과 그와 인접하고 같은 색으로 연결되어 있는 모든 지점의 색을 바꿀 수 있다.
색은 6가지로 색을 선택하였을때, 가장 많이 칠해지며, 색 순서가 작은 색을 선택한다.
이를 반복하고, 모든 판이 같은 색으로 칠해지기 위한 선택 횟수를 출력하라.
위를 DFS로 구현하면서 모든 지점이 색칠되면 선택 횟수를 출력하면 된다.

풀이

// baekjoon 9337 yechan
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int max_n = 21;
const int max_color = 6;
const int dir[4][2] = { { 0, -1}, { 0, 1}, { -1, 0}, { 1, 0}};
int T, N, cnt;
char board[max_n][max_n];
vector<vector<bool> > mark;

void dfs(char color, int x, int y) {
    if (x < 0 || x >= N || y < 0 || y >= N) return;
    if (board[x][y] != color) return;
    if (mark[x][y]) return;

    mark[x][y] = true;
    cnt++;
    for (int d=0; d<4; d++){
        dfs(color, x+dir[d][0], y+dir[d][1]);
    }
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &N);
        memset(board, 0, sizeof(board));
        for (int i=0; i<N; i++) 
            scanf("%s", board[i]);

        vector<vector<bool> > connected(N, vector<bool>(N, false));
        mark = vector<vector<bool> >(N, vector<bool>(N, false));
        cnt = 0;
        dfs(board[0][0], 0, 0);
        connected = mark;
        int maxcnt = cnt;
        vector<int> adjnum(max_color, 0);
        int totalCount = 0;
        while (maxcnt < N * N) {
            maxcnt = 0;
            int maxIdx = -1;
            vector<vector<bool> > maxMark(N, vector<bool>(N, false));
            for (int k=0; k < max_color; k++) {
                for (int i=0; i < N; i++)
                    for (int j=0; j < N; j++)
                        if (connected[i][j])
                            board[i][j] = '1' + k;
                cnt = 0;
                mark = vector<vector<bool> >(N, vector<bool>(N, false));
                dfs(board[0][0], 0, 0);
                if (cnt > maxcnt) {
                    maxcnt = cnt;
                    maxIdx = k;
                    maxMark = mark;
                }
            }
            adjnum[maxIdx]++;
            totalCount++;
            connected = maxMark;
        }
        printf("%d\n", totalCount);
        for (int i=0; i<max_color; i++)
            printf("%d ", adjnum[i]);
        puts("");
    }
    return 0;
}