SW 역량테스트 - [백준] 감시 문제 풀이/해답/코드 (C++ / JAVA)

---

SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다!

해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 

코드에 대한 설명은 주석을 참고해 주세요 :)

 

---

문제 링크 : www.acmicpc.net/problem/15683

해답 코드 : 

 

#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>

using namespace std;

typedef struct cctv {

	int row;
	int col;
	int num;
	int dir;

} cctv;

int N, M;
int map[8][8];
// Up, Right, Down, Left
int dR[4] = {-1, 0, 1, 0};
int dC[4] = {0, 1, 0, -1};
vector<cctv> cctvs;
vector<cctv> cctv_5;
int ans;

bool isRange(int x, int y) {
	if (x < 0 || x >= N || y < 0 || y >= M) {
		return false;
	}
	else return true;
}

void copy_map(int dst[8][8], int src[8][8]) {

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			dst[i][j] = src[i][j];
		}
	}

}

// count zero in the map
void cnt_zero() {
	int zeros = 0;

	for (int i = 0; i < N;i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 0) zeros++;
		}
	}

	ans = min(ans, zeros);
}

// change map : 0 to -1 ( '#' ), according to the direction
void paint_line(int r, int c, int dir) {

	int t_r, t_c, i = dir;

	t_r = r + dR[i];
	t_c = c + dC[i];

	while (isRange(t_r, t_c)) {

		if (map[t_r][t_c] == 0) {
			map[t_r][t_c] = -1;
		}
		else if (map[t_r][t_c] == 6) {
			break;
		} 
		// else : -1, 1, 2, 3, 4, 5
		// just update;

		t_r += dR[i];
		t_c += dC[i];

	}
}

void paint() {

	cctv tv;

	for (int i = 0; i < cctvs.size(); i++) {
		tv = cctvs[i];

		if (tv.num == 1) {
			paint_line(tv.row, tv.col, tv.dir);
		}
		else if (tv.num == 2) {
			paint_line(tv.row, tv.col, tv.dir);
			paint_line(tv.row, tv.col, (tv.dir + 2) % 4);
		}
		else if (tv.num == 3) {
			paint_line(tv.row, tv.col, tv.dir); 
			paint_line(tv.row, tv.col, (tv.dir + 1) % 4);
		}
		else if (tv.num == 4) {
			paint_line(tv.row, tv.col, tv.dir);
			paint_line(tv.row, tv.col, (tv.dir + 1) % 4);
			paint_line(tv.row, tv.col, (tv.dir + 2) % 4);
		}

	}

}

// Allocate direction to each CCTV, with DFS
// 1 : one direction
// 2 : two (180') direction
// 3 : two (90') direction
// 4 : three direction
// 5 : four direction
void monitor(int next) {

	if (next == cctvs.size()) {
		paint();
		cnt_zero();
		return;
	}

	int temp[8][8];

	copy_map(temp, map);

	for (int d = 0; d < 4; d++) {
		
		cctvs[next].dir = d;
		monitor(next+1);
		// restore map
		copy_map(map, temp);

	}


}



int main() {

	cin >> N >> M;

	cctv t_cctv;
	ans = INT32_MAX;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
			if (map[i][j] > 0 && map[i][j] < 5) {
				t_cctv = {i, j, map[i][j], 0};
				cctvs.push_back(t_cctv);
			} 
			// Paint for CCTV 5, beforehand
			else if (map[i][j] == 5) {
				t_cctv = { i, j, map[i][j], 0 };
				cctv_5.push_back(t_cctv);
			}
		}
	}

	// Paint for CCTV 5, beforehand
	cctv tv;
	for (int i = 0; i < cctv_5.size(); i++) {
		tv = cctv_5[i];
		paint_line(tv.row, tv.col, 0);
		paint_line(tv.row, tv.col, 1);
		paint_line(tv.row, tv.col, 2);
		paint_line(tv.row, tv.col, 3);
	}


	monitor(0);

	cout << ans << endl;

}

 

 

SW 역량테스트 준비 - [모의 SW 역량테스트] 풀이 / 코드 / 답안 (C++ / JAVA)

SW 역량테스트 준비 - C++ 코드, Java 코드

SW 역량테스트 준비 - 백준 알고리즘 문제