[알고리즘] 연구소 시리즈 (연구소)

포인트

1. 벽을 세우는 방법을 알아야 한다. for loop 를 사용하는 방법, 재귀를 이용하여 사용하는 방법

만약 수가 정해져 있다면 for loop 가 직관적 일 수 있다.

c++/cpp

for loop 를 이용하여 문제를 해결하는 방법

#include <iostream>
#include <queue>
#include <tuple>

using namespace std;
int n, m;

int map[9][9];
int cmap[9][9];

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};


int bfs() {
    queue<pair<int, int>> q; //bfs 를 위한 큐

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) { 
        // 맵을 복사를 해야 하는 이유
        // 바이러스 상태가 계속 달라지기 떄문이다.
            cmap[i][j] = map[i][j];
            if (cmap[i][j] == 2) q.push(make_pair(i, j));
        }
    }

    while (!q.empty()) {
        int x, y;
        tie(x, y) = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) { //4방향
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue; //범위 체크

            if (cmap[nx][ny] == 0) {
                q.push(make_pair(nx, ny));
                cmap[nx][ny] = 2;
            }
        }
    } // 탐색을 종료하고


    int cnt = 0;
    for (int i = 0; i < n; i++) { // 안전 영역 수를 센다.
        for (int j = 0; j < m; j++) {
            if (cmap[i][j] == 0) cnt+=1;
        }
    }

    return cnt;
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    } //input

    int answer = 0;
    for (int x1 = 0; x1 < n; x1++) { // 벽이 3개 임으로 for loop 를 해주는 것이
        for (int y1 = 0; y1 < m; y1++) {
            if (map[x1][y1] != 0) continue; //이미 벽이면 넘어간다.
            for (int x2 = 0; x2 < n; x2++) {
                for (int y2 = 0; y2 < m; y2++) {
                    if (map[x2][y2] != 0) continue;
                    for (int x3 = 0; x3 < n; x3++) {
                        for (int y3 = 0; y3 < m; y3++) {
                            if (map[x3][y3] != 0) continue;

                            if (x1 == x2 && y1 == y2) continue; //중복 되면 넘어간다
                            if (x2 == x3 && y2 == y3) continue;
                            if (x3 == x1 && y3 == y1) continue;

                            map[x1][y1] = 1;
                            map[x2][y2] = 1;
                            map[x3][y3] = 1; //벽을 세운다.
                            int value = bfs(); // 안전 영역을 확인한다.
                            answer = max(answer, value); // 최대값을 저장 한다.
                            map[x1][y1] = 0; // 벽을 다시 허문다.
                            map[x2][y2] = 0;
                            map[x3][y3] = 0;
                        }
                    }
                }
            }
        }
    }

    cout << answer << '\n';

    return 0;
}

재귀를 이용을 하여 문제를 해결하는 방법

#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
#include <cstring>
using namespace std;

int n, m;
int map[8][8];
int cmap[8][8];

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

vector<pair<int, int>> virus;

int answer;

void bfs() {
	queue<pair<int, int>> q; //x, y
	memcpy(cmap, map, sizeof (map));

	for (auto ele : virus) {
		q.push({ele.first, ele.second});
	}

	while (!q.empty()) {
		int x, y;
		tie(x, y) = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (0 > nx || 0 > ny || nx >= n || ny >= m)
				continue;

			if (cmap[nx][ny] == 0) //빈칸이라면
			{
				q.push(make_pair(nx, ny));
				cmap[nx][ny] = 2; //바이러스 감염
			}
		}
	}

	int cnt = 0; //안전 영역의 수를 센다.
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (cmap[i][j] == 0) {
				cnt += 1;
			}


	answer = max(answer, cnt);
}

void go(int cnt) {
	if (cnt == 3) //벽을 세개 만들었으므로
	{
		bfs();
		return;
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 0) {
				map[i][j] = 1; //마찬가지로 해당칸에 새우고
				go(cnt + 1);
				map[i][j] = 0; //다시 허문다
			}
		}
	}
}

int main() {
	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] == 2) {
				virus.push_back({i, j});
			}
		}


	go(0);

	cout << answer << '\n';

	return 0;
}

 

python

import sys

sys.stdin = open('input.txt')

from collections import deque
from itertools import combinations

n, m = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(n)]

zero, virus = [], deque()
answer = 0
for i in range(n):
    for j in range(m):
        if data[i][j] == 0:
            zero.append((i, j))

        if data[i][j] == 2:
            virus.append((i, j))
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

for wall in combinations(zero, 3):
    copy_data = [data[i][:] for i in range(n)]
    for i in range(3):
        copy_data[wall[i][0]][wall[i][1]] = 1

    # BFS
    q = deque(virus)
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if not (0 <= nx < n and 0 <= ny < m):
                continue

            if copy_data[nx][ny] == 0:
                q.append((nx, ny))
                copy_data[nx][ny] = 2

    summation = 0
    for line in copy_data:
        summation += line.count(0)
    answer = max(answer, summation)

print(answer)