14502.연구소

이번 문제는 연구소이다. 꽤 많이 중요한 내용을 배우고 상기할 수 있는 문제였다.

14502번: 연구소

이 문제를 푸는데 핵심은 맵을 복사해서 사용한다는 것과 나머지는 탐색이다.

난이도는 어려운 수준이 아닌 거 같지만 초보자에게 연습하기는 좋은 문제인 것 같다( 난 초보자 ㅠㅠ.. 너무좋네...)

재귀함수 관련된 문제를 조금 더 풀어봐야할 것 같다.

---

* 문제풀면서 중요한점

1. 문자, 특수기호 실수

=> 실수로 자꾸 if문 다음에 변수에 값을 대입할 때 "=" 대신 "=="를 사용하여 틀림 주의

=> 2중 for문 돌릴 때 변수값을 잘봐야한다 => n과 m인데 n과 n으로 처리하는 경우 주의

 

2. 맞다고 생각한 로직을 조심해라

=> 당연히 맞아야하는데 뭔가 원하는대로 결과가 안나올때는 구현한 로직중에 "여긴 당연히 맞았을거고, 틀린게 없어"라고

     생각한 부분을 다시보거나 다시 생각해라 => 거기가 틀렸을 가능성이 제일 높다!!

 

3. 배열 값 실수

=> MAX 값을 너무 작게 주지 않은건 아닌지 확인해라.

=> 동적할당은 되도록이면 사용하지말자 => 실수할 수도 있고 초기화를 잘못하면 답이 꼬여버림

 

4. freopen은 제출할 때 주석처리 해줘야한다.

 

5. ++ 보다는 +=를 쓰자.

=> 이거 잘못 생각하고 처리하면 답없다..

---

 

< Code 설명 >

//#pragma warning(disable:4996)
#include <iostream>
#include <queue>
#include <algorithm>

#define MAX 9
using namespace std;


int n, m;
int map[MAX][MAX];    // map이 저장되는 공간
int c_map[MAX][MAX];  // map을 복사해서 사용할 공간(map이 변하니까)

int dx[4] = { 0, 0, 1, -1 }; //상하좌우
int dy[4] = { 1, -1, 0, 0 }; //상하좌우

int answer = 0; // 안전한구역의 최대값이 저장될 변수
queue<pair<int, int>> tmp; // virus 좌표가 저장될 큐
 
void copy_map(int (*a)[MAX], int(*b)[MAX]){ // 2차원 배열 복사
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			a[i][j] = b[i][j];
		}
	}
}
void virus_work(){ // 바이러스가 퍼짐 (BFS)
	int virus_map[MAX][MAX];   //바이러스가 퍼질 맵 준비
	copy_map(virus_map, c_map);//벽세운 맵을 바이러스가 퍼질맵에 복사

	queue<pair<int, int>> virus;// 바이러스 좌표가 저장될 큐
	virus = tmp; // 처음에 저장한 좌표를 옮김(바이러스 퍼지면 큐가 사라지기때문에)

	while (!virus.empty()){ 
		int x = virus.front().first; // x좌표
		int y = virus.front().second;// y좌표 옮기고
		virus.pop();  // pop 해줌
		for (int i = 0; i < 4; i++){ //상하좌우 탐색
			int ax = x + dx[i];
			int ay = y + dy[i];

			if (ax < 0 || ay < 0 || ax > n || ay > m) //맵 내에 존재해야함
				continue; // 그게아니면 넘어가
			if (virus_map[ax][ay] == 0){ // 안전한 공간이 있으면
				virus_map[ax][ay] = 2;   // 바이러스로 뒤덮음
				virus.push(make_pair(ax, ay)); // 그리고 덮은 좌표들 큐에저장
			}
		}
	}
	int cnt = 0; // 안전한 공간이 cnt될 변수
	for (int i = 0; i < n; i++){     
		for (int j = 0; j < m; j++){
			if (virus_map[i][j] == 0) // 안전한 공간이 있다면
				cnt += 1; // count 한다.
		}
	}
	answer = max(answer, cnt); // 최대값 구함
}
void wall(int cnt){ // 백을 세우는 로직 (재귀함수)
	if (cnt == 3){  // 탈출 구문 => 벽이 3개면
		virus_work(); // 바이러스 작동
		return; // 탈출
	}

	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			if (c_map[i][j] == 0){ // 안전한 공간이면
				c_map[i][j] = 1;   // 벽을 세움
				wall(cnt + 1);     // 다음벽을 세우기 위한 재귀
				c_map[i][j] = 0;   // 그 다음 조합을 위해 0으로 초기화
			}
		}
	}
}
int main() {
	//freopen("14502.txt", "r", stdin); // 디버깅용
	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) // 바이러스 좌표 미리 저장
				tmp.push(make_pair(i, j));
		}
	}

	copy_map(c_map, map); // 맵을 복사함
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			if (map[i][j] == 0){ // 0일 경우
				c_map[i][j] = 1; // 벽을 세움
				wall(1);         // 하나 세웠으니까 1로시작
				c_map[i][j] = 0; // 다음 조합을 위해 0으로 초기화
			}
		}
	}
	cout << answer << "\n";
	return 0;
}