[백준/C++] 연구소_14502_G4

📝 문제

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

💻 코드

#include <iostream>
#include <queue>

using namespace std;

struct Node {
	int row;
	int col;
};

int arr[10][10] = { 0, };  // 연구소의 지도
int n, m;
int mmax = 0;

void bfs() {
	int dr[] = { 0, 0, 1, -1 };
	int dc[] = { 1, -1, 0, 0 };
	int copy[10][10];
	queue<Node> q;  // 바이러스 저장할 큐

	// 연구소 지도 복사
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			copy[i][j] = arr[i][j];
			// 바이러스 위치 저장
			if (copy[i][j] == 2) {
				q.push({ i, j });
			}
		}
	}

	// 바이러스 감염
	while (!q.empty()) {
		Node now = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nextRow = now.row + dr[i];
			int nextCol = now.col + dc[i];
			// 범위 벗어남
			if (nextRow < 0 || nextCol < 0 || nextRow >= n || nextCol >= m) continue;
			// 빈 칸이 아닌경우
			if (copy[nextRow][nextCol] == 2 || copy[nextRow][nextCol] == 1) continue;

			copy[nextRow][nextCol] = 2;
			q.push({ nextRow, nextCol });
		}
	}
	// 안전영역 카운트
	int sum = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (copy[i][j] == 0) {
				sum += 1;
			}
		}
	}

	if (sum > mmax) mmax = sum;
}

void walls( int cnt) {
	// 벽을 다 세웠으면 감염
	if (cnt == 3) {
		bfs();
		return;
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 0) {
				arr[i][j] = 1;
				walls(cnt + 1);
				arr[i][j] = 0;
			}
		}
	}
}

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

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

	// 벽 세우기
	/*for (int i  = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 0) {
				arr[i][j] = 1;
				walls(i, j, 1);
				arr[i][j] = 0;
			}
		}
	}*/
	walls(0);

	cout << mmax;
	return 0;
}

📌 해결방법

바이러스가 상하좌우로 1칸씩 퍼진다고 설명해서 bfs가 떠올랐다.
감염전에 벽을 3개 반드시 세워야 되니깐 재귀함수로 벽을 세우고 3개를 다 세웠을 때 bfs를 실행해서 안전영역을 계산한다.
주의할점: 연구소 지도를 원본 사용X

💡 배운 점

벽을 세울 때 for문을 잘못 짜서 시간을 많이 씀..
walls의 인자로 앞에 세운 벽의 좌표를 받아서 그 이후의 범위만 보려고 아래 코드와 같이 짰는데 j가 항상 y에서 시작에서 y보다 작은 범위를 검사하지 않는 문제가 발생했었다.

void walls(int x, int y, int cnt) {
	// 벽을 다 세웠으면 감염
	if (cnt == 3) {
		bfs();
		return;
	}

	for (int i = x; i < n; i++) {
		for (int j = y; j < m; j++) {
			if (arr[i][j] == 0) {
				arr[i][j] = 1;
				walls(i,j,cnt + 1);
				arr[i][j] = 0;
			}
		}
	}
    
    ----------------------------------- 수정
    for (int i = 0; i < n; i++){
    	for (int j = 0; j < m; j++){
           if (arr[i][j] == 0) {
                  arr[i][j] = 1;
                  walls(i,j,cnt + 1);
                  arr[i][j] = 0;
              }
		}
	}
    ------------------------------------- i = x, j =0 가능
}