[풀이]백준 풀이(XIII/15683 등)

문제풀이

감시(15683, 시뮬레이션)

  • N*M 형태의 이차원 배열
  • CCTV는 5가지 종류(1한방향, 2양쪽방향, 3직각방향, 4세방향, 5네방향)
  • 6은 벽이다.

  • 사무실의 크기와 상태, CCTV가 주어졌을 때 CCTV의 방향을 적절히 정해서 최소 사각지대의 크기를 구하는 프로그램을 작성하라.

  • 1<=N,M <=8
  • CCTV는 8개를 넘지 않는다.

풀이

  • 중복순열이 필요하다 (next_permutation은 그냥 순열!)
  • 백준15651 참조!
  • 외울게 늘었네 ㅎㅎ.. (DFS를 이용한 순열구하기!)

DFS를 짜되 VISITED를 표시하지 않으면 된다.

문법…헷갈려 아래 둘은 같은 뜻

      for (auto i : vc)
          printf("%d ", i);
      printf("\n");
      return;

        int size = vc.size();
    
    	for(int i=0; i<size; i++){
    		cout << vc[i] << " ";
    	}
    	cout << endl;
    	return;

중단

회고

  • 사람은 실수를 한다…
  • 시험장가서도 이럴거같은데 걱정이네.

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>

#define NEWS 4
#define INF 987654321
using namespace std;

int cx, cy;
int n, m, cctv, Answer = INF;
int office[9][9];
int officeTemp[9][9];
vector<int> vc;
//<type, cx, cy>
queue<tuple<int, int, int>> tv;
queue<tuple<int, int, int>> tvTemp;
queue<int> rotateInfo;


//이게 0부터가면 되는게 아니라 
void watchLeft(int x, int y) {
	if (office[x][y - 1] == 6) return;
	for (int i = y; i >= 0; i--) {
		//벽이면 끝내
		if (office[x][i] == 6) {
			i = -1;
		}
		//아니면 -1(#)으로 채우자
		else if (office[x][i] == 0)  office[x][i] = -1;
	}
}
void watchRight(int x, int y) {
	if (office[x][y +1] == 6) return;
	for (int i = y; i < m; i++) {
		//벽이면 끝내
		if (office[x][i] == 6) i = m;
		//아니면 -1(#)으로 채우자
		else if (office[x][i] == 0)  office[x][i] = -1;
	}
}
void watchUp(int x, int y) {
	if (office[x-1][y] == 6) return;

	for (int i = x; i >= 0; i--) {
		//벽이면 끝내
		if (office[i][y] == 6) i = -1;
		//아니면 -1(#)으로 채우자
		else if (office[i][y] == 0)  office[i][y] = -1;
	}
}
void watchDown(int x, int y) {
	if (office[x +1][y] == 6) return;
	for (int i = x; i < n; i++) {
		//벽이면 끝내
		if (office[i][y] == 6) i = n;
		//아니면 -1(#)으로 채우자
		else if (office[i][y] == 0)  office[i][y] = -1;
	}
}

void makeBlindSpot(int type, int degree) {
	if (type == 1)
	{
		//R
		if (degree == 1)watchRight(cx, cy);
		//D
		if (degree == 2)watchDown(cx, cy);
		//L
		if (degree == 3)watchLeft(cx, cy);
		//U
		if (degree == 4)watchUp(cx, cy);

	}
	if (type == 2)
	{
		//LR
		if (degree % 4 == 1) {
			watchLeft(cx, cy);
			watchRight(cx, cy);
		}
		//UD
		if (degree % 4 == 2) {
			watchUp(cx, cy);
			watchDown(cx, cy);
		}

	}
	if (type == 3)
	{
		//UR
		if (degree == 1) {
			watchUp(cx, cy);
			watchRight(cx, cy);
		}
		//RD
		if (degree == 2) {
			watchRight(cx, cy);
			watchDown(cx, cy);
		}
		//DL
		if (degree == 3) {
			watchDown(cx, cy);
			watchLeft(cx, cy);
		}
		//LU
		if (degree == 4) {
			watchLeft(cx, cy);
			watchUp(cx, cy);
		}

	}
	if (type == 4)
	{
		//LUR
		if (degree == 1) {
			watchLeft(cx, cy);
			watchUp(cx, cy);
			watchRight(cx, cy);
		}
		//URD
		if (degree == 2) {
			watchUp(cx, cy);
			watchRight(cx, cy);
			watchDown(cx, cy);

		}
		//RDL
		if (degree == 3) {
			watchRight(cx, cy);
			watchDown(cx, cy);
			watchLeft(cx, cy);
		}
		//DLU
		if (degree == 4) {
			watchDown(cx, cy);
			watchLeft(cx, cy);
			watchUp(cx, cy);
		}
	}
}

void findBlindSpot() {
	int compAns = 0;
	int type;
	int degree;
	while (!rotateInfo.empty())
	{
		//tv = cctv 종류 && 위치
		//rotateInfo = 회전(방향) (1 = 90, 2 = 180, 3 = 270)
		tuple<int, int, int> k = tv.front();
		tie(type, cx, cy) = k;
		degree = rotateInfo.front();

		if (cx == 2 && cy == 3 && type == 1 && degree == 3) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (office[i][j] == 0) compAns++;
				}
			}
		}
		if (type != 6)	makeBlindSpot(type, degree);

		//큐에서 빼고
		tv.pop();
		rotateInfo.pop();
	}
	//tv 비워보자..
	while (!tv.empty()) {
		tv.pop();
	}
	//사각지대를 찾고
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (office[i][j] == 0) compAns++;
		}
	}
	Answer = min(Answer, compAns);
	//tv 갱신
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			office[i][j] = officeTemp[i][j];
			if (office[i][j] > 0 && office[i][j] != 6) {
				tv.push(tuple<int, int, int>(office[i][j], i, j));
			}
		}
	}
}
void dfs()
{
	//예외1 만약 현재최소값이 0이면 더작아질 수 없으므로 끝낸다.
	if (Answer == 0) {
		return;
	}

	//cctv 개수
	cctv = tv.size();
	int size = vc.size();
	if (size == cctv)
	{
		//회전정보 저장
		for (int i = 0; i < size; i++) {
			rotateInfo.push(vc[i]);
		}
		//사각지대를 찾는다.
		findBlindSpot();
		return;
	}

	for (int i = 1; i <= NEWS; i++)
	{
		if (size < cctv)
		{
			vc.push_back(i);
			dfs();
			vc.pop_back();
		}
	}
}
int main()
{
	int Atemp = 0;
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> office[i][j];
			//카메라가 없는 경우를 대비하여 미리 처리
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (office[i][j] == 5) {
				watchUp(i, j);
				watchRight(i, j);
				watchDown(i, j);
				watchLeft(i, j);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {

			officeTemp[i][j] = office[i][j];
			//카메라가 하나도 없을 경우에 대비해서
			if (office[i][j] == 0) Atemp++;
			if (office[i][j] > 0) {
				if (office[i][j] != 6)	tv.push(tuple<int, int, int>(office[i][j], i, j));
			}

		}
	}
	//미리 0의 개수를 세놓는다.
	Answer = min(Atemp, Answer);
	dfs();
	cout << Answer;
	return 0;
}

계란으로 계란치기(16987)

  • 계란은 내구도, 무게를 가지고 있다.
  • 계란끼리 부딪히면 상대의 무게만큼 내구도가 깎인다.

  • 내구도가 0이하가 되면 계란은 깨진다.

  • 가장 왼쪽 계란부터 시작
  • 깨지지 않은 다른 계란 중 하나를 친다.
    • 모든 계란이 깨졌다면 PASS
    • 손에 든 계란이 깨졌다면 PASS
  • 가장 최근에 든 계란의 한 칸 오른쪽 계란을 들고 깨지지 않은 계란 중 하나를 친다.

  • 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 종료한다.

  • 최대한 많은 계란을 깨고싶다.

ㅇ ㅇ ㅇ ㅇ ㅇ ㅇ 맨 왼쪽거 들고 랜덤으로 친다. 원래 자리에 내려놓고 다음 계란을 든다. 즉, 모든 계란으로 한 번씩 칠 수도 있다.

연습하기 int형태 dfs 짜기

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

int n;
//index, durability, weight
queue<tuple<int, int, int>> eggs;
vector<tuple<int, int, int>> eggsTemp;

vector<pair<int, int>> dw;
vector<int> arrForNP;
bool destroyed[8];
int durable[8];
int weight[8];
int Answer = 0;
int result = 0;

bool isDestroyed(int x) {
	if (durable[x] <= 0) {
		destroyed[x] = true;
		return true;
	}
	else {
		destroyed[x] = false;
		return false;
	}
}

bool isAllDestroyed(int hand) {
	for (int i = 0; i < n; i++) {
		if (durable[hand] == i) continue;
		else if (durable[i] > 0) return false;
	}
	return true;
}

bool isFight(int x, int y) {
	if (!isDestroyed(x) && !isDestroyed(y) ) return true;
	else return false;
}

bool isInside(int hand) {
	if (hand < n) return true;
	else return false;
}

void printState(int hand, int i) {



	for (int i = 0; i < n; i++) {
		int tmp = 0;
		if (durable[i] <= 0) tmp++;
		result = max(result, tmp);
	}
}

void collide(int hand) {
	//중복이 허용이 돼야한다.

	for (int i = 0; i < n; i++) {
		//손에 들었으므로 자기자신은 제외
		if (hand == i) continue;
		if (!isInside(hand)) return;
		else {
			//모든 계란이 깨졌다. 또는 마지막 계란까지 다 쳤으면
			if (isAllDestroyed(hand) || hand==n+1) {
				printState(hand, i);
				result = max(result, Answer);
				return;
			}
			else {
				//안깨진놈들끼리면
				if (isFight(hand, i)) {
					//부딪혔으면 서로 빼라.

					durable[hand] -= weight[i];
					durable[i] -= weight[hand];
					bool handTmp = false;
					bool iTmp = false;
					if (isDestroyed(hand)) {
						Answer++;
						handTmp = true;
					}
					if (isDestroyed(i)) {
						Answer++;
						iTmp = true;
					}
					//손에든걸로 다음꺼 부쉈으면 다다음껄로 시작
					if ( (i-hand)==1 && isDestroyed(i)) {
						collide(hand + 2);
					}
					else {
						collide(hand + 1);
					}
					printState(hand, i);
					result = max(result, Answer);
					//원상복구 (여기서 부숴졌으면 돌려놔)
					if (isDestroyed(hand) && handTmp) Answer--;
					if (isDestroyed(i) && iTmp) Answer--;
					durable[hand] += weight[i];
					durable[i] += weight[hand];
				}
			}
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int j, k;
		cin >> j >> k;
		durable[i] = j;
		weight[i] = k;
	}

	collide(0);

	cout << result;

}

댓글남기기

참고