[백준] 15683번 감시

문제: 15683번: 감시

basic-algo-lecture/workbook/0x0D.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x0D.md at master · encrypted-def/basic-algo-lecture

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>
#include <list>
#include <sstream>
#include <tuple>

using namespace std;

int n, m; // n: 세로, m: 가로
int cctvCnt = 0;

// 0: 빈칸, 6: 벽, 1~5: CCTV
int board[8][8]; // max 가 8 

// 각 cctv 가 가진 방향에 cctvDir 의 idx 넣어줘서 공용으로 쓰면 될 듯?
pair<int, int> cctvDir[4] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
// cctv 맨 처음 시작 방향
tuple<int, int, int, int> dirList[5] = { {0, -1, -1, -1}, {0, -1, 2, -1}, {0, 1, -1, -1}, {0, 1, 2, -1}, {0, 1, 2, 3} };


// 0: cctv 번호, 1: cctv 좌표, 2: cctv 방향 번호
vector<tuple<int, pair<int, int>, tuple<int, int, int, int>>> cctvs;

int minCnt = 100;


void Run(int dirKey, bool flag, pair<int, int> curCCTVPos, queue<pair<int, int>>& visit) {
	if (dirKey == -1) return; // -1 이면 걍 빠져나가~~

	int nx = curCCTVPos.first;
	int ny = curCCTVPos.second;

	while (true) {
		nx += cctvDir[dirKey].first;
		ny += cctvDir[dirKey].second;

		// 범위 벗어나면 걍 빠져나가
		if (nx < 0 || nx >= m || ny < 0 || ny >= n) break;

		// 벽이면 빠져나가
		if (board[ny][nx] == 6) break;

		// cctv면 빠져나가
		if (1 <= board[ny][nx] && board[ny][nx] <= 5) continue;

		// 0 이면 쏘기
		if (flag == 0) {
			if (board[ny][nx] == 0) {
				board[ny][nx] = -1; // cctv 쏴~
				visit.push(make_pair(nx, ny));
			}
		}
		else if (flag == 1) {
			while (!visit.empty()) {
				pair<int, int> pos = visit.front();
				visit.pop();

				board[pos.second][pos.first] = 0; // 원상태로..
			}
		}
	}
}


void WorkCCTV(bool flag, pair<int, int> curCCTVPos, tuple<int, int, int, int> curCCTVDirs, queue<pair<int, int>>& visit) {
	// cctv 돌려
	int dirKey = get<0>(curCCTVDirs);
	Run(dirKey, flag, curCCTVPos, visit);


	dirKey = get<1>(curCCTVDirs);
	Run(dirKey, flag, curCCTVPos, visit);


	dirKey = get<2>(curCCTVDirs);
	Run(dirKey, flag, curCCTVPos, visit);


	dirKey = get<3>(curCCTVDirs);
	Run(dirKey, flag, curCCTVPos, visit);
}


int Update(int dir) {
	if (dir == -1) return dir;

	return (dir + 1) % 4;
}

tuple<int, int, int, int> UpdateDirs(tuple<int, int, int, int> curCCTVDirs) {
	// cctv 회전 반영
	int dir1 = Update((get<0>(curCCTVDirs)));
	int dir2 = Update((get<1>(curCCTVDirs)));
	int dir3 = Update((get<2>(curCCTVDirs)));
	int dir4 = Update((get<3>(curCCTVDirs)));

	return make_tuple(dir1, dir2, dir3, dir4);
}


// CCTV 다 쓰면 Funct 빠져나오도록
void Funct(int step) {
	if (step == cctvCnt) {
		int tmp = 0;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (board[i][j] == 0) {
					tmp++;
				}
			}
		}
		if (tmp < minCnt)
			minCnt = tmp; // 갱신

		return;
	}

	int curCCTVKey = get<0>(cctvs[step]);
	pair<int, int> curCCTVPos = get<1>(cctvs[step]);
	tuple<int, int, int, int> curCCTVDirs = get<2>(cctvs[step]);

	int loopCnt = 0;

	// 네 방향으로 돌려보기
	for (int i = 0; i < 4; i++) {
		queue<pair<int, int>> visit; // 음.. cctv 돌기 전에 이미 -1 이었던 곳은 저장해놓고 원상태로 되돌릴 때 그곳은 0으로 돌리면 안 됨.

		WorkCCTV(0, curCCTVPos, curCCTVDirs, visit); // cctv 쏘기
		Funct(step + 1);
		WorkCCTV(1, curCCTVPos, curCCTVDirs, visit); // 원래 상태로 돌려내기..

		loopCnt++;
		if (loopCnt == 1 && curCCTVKey == 5) break; // 5번 cctv 는 한 번만 돌면 됨
		if (loopCnt == 2 && curCCTVKey == 2) break; // 2번 cctv 는 2번만 돌면 됨

		curCCTVDirs = UpdateDirs(curCCTVDirs);
	}
}


int main() {
	ios_base::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 >> board[i][j];

			// cctv 개수 세기
			if (1 <= board[i][j] && board[i][j] <= 5) {
				cctvCnt++;

				int cctvKey = board[i][j];
				pair<int, int> cctvPos = make_pair(j, i); // x, y
				tuple<int, int, int, int> dirs;

				dirs = dirList[cctvKey - 1];
				// cctv 정보 저장
				cctvs.push_back(make_tuple(cctvKey, cctvPos, dirs));
			}
		}
	}
	Funct(0);
	cout << minCnt;


	return 0;
}

 

... 한 문제를 3시간 넘게 풀었다. 백트래킹을 이용하면 풀 수 있는 문제긴 한데 구현이 너무 짜증났다. 초기 방향 설정도 해줘야 하고 90도씩 돌려줘야하고....;;;

 

각 재귀마다 4가지 경우로 파고들어가면 된다. 0도, 90도, 180도, 270도로.. 근데 2번 CCTV 는 0, 90도로 2가지 경우 5번 CCTV 는 0 도로 1가지 경우만 하면 된다. 왜냐면 더 돌리면 이전이랑 겹쳐서 중복되니가 시간 낭비..

 

실수했던 부분은 cctv 돌렸던 보드판을 원상태로 돌리는 부분이었다. 그냥 단순히 cctv 가 쏜 곳을 다시 0으로 쏘니까 문제가 났다. 왜냐면 다른 cctv 가 쐈던 부분까지 0으로 바꿔버리는 경우가 있어서(예를들어 2개의 cctv 가 쏜 구역이 같을 때 위와 같은 방법으로 하면 하나의 cctv 를 지운거지만 다른 하나까지 같이 지워져서 망한거였다.)

 

그래서 현재 cctv 가 쏘는 곳이 이미 1이면 큐에 안 넣고, 0이면 큐에 넣도록 했다. 큐는 각 단계마다 가지도록 했다. 큐를 전체가 같이 쓰면 그것도 오류나서..

 

ㅠ_ㅠ;;;;;;;;; 너무 생각해야할게 많은 문제였다.

 

 

 

참고자료:

[바킹독의 실전 알고리즘] 0x0D강 - 시뮬레이션

 

[C++] tuple 사용법 & 예제

[C++] tuple 사용법 & 예제