[백준 14502번] 연구소

http://www.acmicpc.net/problem/14502

14502번: 연구소

풀이) 

빈 칸 모든 자리에 벽을 3개씩 세우는 방식으로 접근하였다. 헷갈리지 않게 하기 위해서, 사이즈를 +2씩 잡고 전체를 벽으로 둘러줬다. 이후 벽이 3개가 모두 채워지면 dfs를 돌려서 바이러스를 채워주었고, 이후 남아있는 공간을 세는 방식으로 구현하였다. 

#include <iostream>
using namespace std;

int N, M, virus_n = 0, cnt = -1, temp = 0, wall_sum = 0;
int MAP[11][11], MAP_c[11][11], visited[11][11] = {0,}, virus[11];
int dir_x[4] = {-1, 0, 1, 0};
int dir_y[4] = {0, -1, 0, 1};

void init()
{
    cin >> N >> M;
    for (int i = 0; i <= N + 1; i++)
    {
        for (int j = 0; j <= M + 1; j++)
        {
            if (i == 0 || i == N + 1 || j == 0 || j == M + 1)
                MAP[i][j] = MAP_c[i][j] = 1;
            else
            {
                cin >> MAP[i][j];
                if (MAP[i][j] == 2)
                    virus[virus_n++] = i * 10 + j;
                MAP_c[i][j] = MAP[i][j];
            }
        }
    }
}

void dfs(int x, int y) 
{
    for (int i = 0; i < 4; i++)
    {
        if (!MAP[x + dir_x[i]][y + dir_y[i]] && !visited[x + dir_x[i]][y + dir_y[i]])
        {
            visited[x + dir_x[i]][y + dir_y[i]] = 1;
            MAP[x + dir_x[i]][y + dir_y[i]] = 2;
            dfs(x + dir_x[i], y + dir_y[i]);
        }
    }
}

void solve()
{
    for (int wall_1 = 1; wall_1 <= N * M; wall_1++)
    {
        for (int wall_2 = wall_1 + 1; wall_2 <= N * M; wall_2++)
        {
            for (int wall_3 = wall_2 + 1; wall_3 <= N * M; wall_3++)
            {
                if (wall_1 % M == 0 && !MAP[wall_1 / M][M])
                {
                    MAP[wall_1 / M][M] = 1;
                    wall_sum++;
                }
                else if (!MAP[wall_1 / M + 1][wall_1 % M])
                {
                    MAP[wall_1 / M + 1][wall_1 % M] = 1;
                    wall_sum++;
                }

                if (wall_2 % M == 0 && !MAP[wall_2 / M][M])
                {
                    MAP[wall_2 / M][M] = 1;	
                    wall_sum++;
                }
                else if (!MAP[wall_2 / M + 1][wall_2 % M])
                {
                    MAP[wall_2 / M + 1][wall_2 % M] = 1;
                    wall_sum++;
                }	
				
                if (wall_3 % M == 0 && !MAP[wall_3 / M][M])
                {
                    MAP[wall_3 / M][M] = 1;
                    wall_sum++;
                }
                else if (!MAP[wall_3 / M + 1][wall_3 % M])
                {
                    MAP[wall_3 / M + 1][wall_3 % M] = 1;
                    wall_sum++;
                }

                if (wall_sum == 3)
				{
					for (int i = 0; i < virus_n; i++)
						dfs(virus[i] / 10, virus[i] % 10);
					for (int i = 0; i <= N + 1; i++)
					{
						for (int j = 0; j <= M + 1; j++)
						{
							if (!MAP[i][j])
								temp++;
							visited[i][j] = 0;
							MAP[i][j] = MAP_c[i][j];
						}
					}
					if (temp > cnt)
						cnt = temp;
					temp = 0;
				}
				else
				{
					for (int i = 0; i <= N + 1; i++)
					{
						for (int j = 0; j <= M + 1; j++)
						{
							visited[i][j] = 0;
							MAP[i][j] = MAP_c[i][j];
						}
					}
				}
				wall_sum = 0;
			}
		}
	}
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    init();
	solve();
    cout << cnt;
	return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!