프밍노트

 

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

 

 

 

통학이 너무나도 하기 싫었던 영우는 결국 학교의 기숙사에 들어갔다. 통학의 고통에서 해방된 기쁨도 잠시, 학교 기숙사에서는 일정 기간마다 청소 검사를 한다는 사실을 알게 되었다. 청소 검사에서 나쁜 점수를 받으면 벌점을 받게 되고, 벌점이 많이 쌓이면 기숙사에서 퇴사 해야 한다. 영우는 어떤 경우에 벌점을 받는지 궁금하여 기숙사에서 진행하는 청소 검사 시스템에 대해 자세히 조사해 보았다. 기숙사 청소 검사 시스템은 오늘로부터 정확히 t 일이 지나고 검사를 하며, 검사 시간 단축을 위해 방의 특정 부분만 검사한다. 하지만 검사하는 특정 부분 중 한 곳이라도 더럽다면 영우는 벌점을 받게 된다. 영우가 사는 방은 N * N 정사각형 방이며, 기숙사 방바닥에는 곰팡이가 서식하고 있다. 곰팡이는 1 일이 지날 때마다 특이한 방식으로 증식하는데, 그림 1(a)의 곰팡이는 1 일이 지나면 그림 1(b)와 같이 8 군데로 증식되고, 원래의 곰팡이는 사라진다. 만약 곰팡이가 증식해야 하는 부분이 벽으로 막혀 있다면, 그곳으로는 증식하지 못한다. 그림 2 는 두 군데의 곰팡이가 1 일이 지난 후 모습이다.

 

위 그림은 증식방식이다.

 

 

 

해당문제는 처음 보았을때 단순 시물레이션 문제와 같다고 생각할수 있지만

 

그냥 구현하게 된다면  반복적인 처리로인해 계산해야 하는 곰팡이가 기하급수적으로 늘어난다

 

해당 문제를 잘 생각해본다면 최적화 할수있는 부분이 쉽게 보인다.

 

 

 

중앙에서 시작할경우 퍼지는 모습은 아래와 같다

 

 

위 이미지로 알수있는것은  이동 했던 칸에서 다시 원래자리에 곰팡이를 복구 시킨다는 사실이다.

 

그렇다면 해당 위치에 곰팡이가 생기고 하나라도 이동했을경우엔 무한정 곰팡이가 번식한다는 이야기다...으...

 

 

그렇다면 두번째로 생각할수있는것은 

 

해당 위치에서 1턴 쉬면서 반복한다 라는것은 

 

홀수날과 짝수날을 구분지어 두개의 영우의방을 돌아가면 계산한다면,

해당 위치가 이미 곰팡이가 있었던 적이 있었는지도 간단하게 체크할수있다.

 

 

BFS를 사용해서 반복체크를 할때 다음 날의 위치가 일전에 도달한적 있는 위치라면

 

이미 반복했던 위치기에 다시 곰팡이를 그릴 이유가 없다.

 

 

 

 

 

 

하지만 해당 문제는 쉽게 지나칠수 있는 문제가 존재한다.

바로 마지막줄인 "만약 곰팡이가 증식해야 하는 부분이 벽으로 막혀 있다면, 그곳으로는 증식하지 못한다."

 

해당 문제에서 증식 하지못한다면 자연적으로 사라진다.

 

곰곰히 생각해보면 3*3의 가운데 지점 에서만 문제가 될수있다.

 

그 미만(2*2 ,1*1)에서는 곰팡이는 생존이 불가능하고

 

초과되었을때는 어느 장소에 생겨도 한무반복은 예정되어있다.

 

 

 

예외 예제를 보자 

해당위치는 3*3이상에서 의 유일한 사라지는 위치다. 이부분만 조심해서 문제를 풀자.

 

 

 

프로그램의 입력은 표준 입력으로 받는다. 첫 줄에 영우의 방의 크기, 방에 있는 곰팡이의 개수, 청소 검사 시스템이 검사하는 방바닥 좌표의 개수, 청소 검사가 실시 되기까지 남은 일수인 N M K t 가 주어진다.

(1 ≤ N ≤ 300, 0 ≤ M ≤ N2, 0 ≤ K ≤ N2, 1 ≤ t ≤ 10000)

 

둘째 줄부터 M 개의 줄에 걸쳐 영우의 방에 있는 곰팡이의 위치인 Mx My가 주어진다.(1 ≤ Mx, My ≤ N)

다음 줄부터 K 개의 줄에 걸쳐 검사관이 검사하는 방바닥의 위치인 Kx Ky가 주어진다.(1 ≤ Kx, Ky ≤ N)

 

 

N 영우의 방크기

M 방에있는 곰팡이의 개수

K 검사하는 방바닥 좌표의개수

t  청소 검사가 실시 되기까지 남은 일수

 

 

5 2 4 1

 

2 1

3 3

 

3 1

3 2

3 3

3 4

 

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void ClearRoom() {

	int N, M, K, t;
	cin >> N >> M >> K >> t;
	std::vector<vector<bool>> vmap(N + 1, vector<bool>(N + 1, false)),
		avmap(N + 1, vector<bool>(N + 1, false)),
		* Nextpm, * Dpm;
	std::queue <int> QSearchX;
	std::queue <int> QSearchY;


	int x = 0, y = 0;
	for (int i = 0; i < M; i++)
	{
		cin >> x >> y;
		vmap[--x][--y] = true;
		QSearchX.push(x);
		QSearchY.push(y);
	}

	const int dy[8] = { -1,-2,-2,-1,1,2,2,1 };
	const int dx[8] = { -2,-1,1,2,2,1,-1,-2 };
	for (int i = 0; i < t; ++i) {

		int Qsize = QSearchX.size();
        
        //오늘 방과 내일 영우의 방
		Dpm = &(((i % 2) != 0) ? avmap : vmap);
		Nextpm = &(((i % 2) == 0) ? avmap : vmap);
		//현재 일수에 움직이는 곰팡이
        for (int j = 0; j < Qsize; j++)
		{
			int datax = QSearchX.front();
			int datay = QSearchY.front();
			QSearchX.pop();
			QSearchY.pop();
			bool check = false;
            
            //8방향 곰팡이 번식
			for (int i = 0; i < 8; ++i) {
				x = datax + dx[i];
				y = datay + dy[i];
				
                //곰팡이 가 번식 가능한지 확인후 번식
                if ((x < N && x >= 0 && y < N && y >= 0) && !(*Nextpm)[x][y])
				{
                	(*Nextpm)[x][y] = true;
                    // 다음 번식 예정인 queue
					QSearchX.push(x);
					QSearchY.push(y);
					check = true;
				}
			}
            //만약 해당 곰팡이가 어느 하나도 이동하지 못햇더라면
            //이 곰팡이는 다음날 죽는다.
			if (!check) {
				(*Dpm)[datax][datay] = false;
			}
		}
	}
	bool IsClear = false;
	Dpm = &(((t % 2) != 0) ? avmap : vmap);
    
    //검수의 날
	for (int i = 0; i < K; i++)
	{
		cin >> x >> y;
		if ((*Dpm)[x-1][y-1])IsClear = true;
		if (IsClear)break;
	}
	cout << (IsClear ? "YES" : "NO");
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	ClearRoom();
}

 

 

 

해당 문제를 풀며 

배열 문제의 1입력 과 0입력을 확실하게 잡아야했고

 또한 문제 t의 정의에 대해 확실하게 잡아야했다.

 

 

 

 

아래 시뮬레이터로 문제의 경우의 수를 확인해보자

 

 

 

영우가 빠른시일 내로 청소하지 않는다면 집은 곰팡이에게 잠식당해 버릴지도 모른다.

 
처음 풀어보는 백준의 플래티넘 문제.
 
내가 풀었던 방식 부터 적을 생각이다.
 
우선 문제는 이름 그대로 최단 경로가 아닌 거의 최단 경로를 찾는다.
그래프에서 최단경로들의 간선을 제외한 그다음에 나오는 최단경로를 찾는 문제
 
우선 생각했던 방법은 다익스트라로 간선들을 지우면서 나간뒤 다익스트라를 한번더 돌릴예정이였다.
 
그렇게 테스트 하였지만 결과는 8% 실패
 
 
 
실패 이유는 다익스트라로 간선을 지울경우 간선이 하나만 지워지는 문제가 생긴다.
 

 
위 의경우  최단경로는 두개로   1 2 4 5 와  1 3 4 5가 있다.
 
거의 최단경로는 저두개를 제외한 1 ->5인  이여야 하지만
 
경로를 먼저 지워주게 될경우 4->5가 공유되지않으면서
거의최단경로는 6이 나오게된다. 
 

 
정상적인경우 위처럼 최단경로들을 제외하여 4->5로가는 길을 쓸수없기에  7이 나오지 못한다.
 
 
두번째 아이디어는 지나가면서 모든 지나온 간선  1->2 일경우 tuple<1,2> 식으로 queue 에 담아간뒤
 

마지막 칸에 도착하였을경우 최적해로 도착한 queue내부의 간선중 지워지지 않은 간선을 지워주었다.
 
문제에서 실패는 없었지만 25%에서 메모리 초과가 났다.
 
 
 
 
여기서 한동안 고민을 하다. 문제를 알아냈다.
 
문제는 메모리 초과 
 
queue로 간선을 담으면서 갈경우 특정 노드에서 만나는경우 왔던 간선을 유지하기위해
최단거리가 두개가 같은노드에서 만나면 둘다 큐에 넣어주었다.

 
위 같이 이런경우 같은 노드에 만나는 경우 이후 노드의 값만큼 의미없는 계산이 기하급수적으로 늘어날수 있다.
이후 계산은 전부 똑같지만 일전의 계산때문에 그전 간선이 다른 만큼 계산이 늘어남
 
 
 
 
문제를 해결하기위해 코드를 크게 변경해주었다.
 
우선 다익스트라를 돌며 같은 중간노드에서 같은 값이 있을경우 를 해결하기위해
 
다익스트라에서  현재위치의 크기를 알아야 한다.
그뒤 현재 노드로 온 그전 노드의 위치를 알수있어야 한다.
 

 

 

 

 

이렇게 만든경우
최소 큐 에서  더큰 같은 크기의 거리에서 만난 경우 그냥 그 위치에 왔던 노드를 표시해준다면
도착한뒤 돌아가면서 간선 제거를 해준다면

 

위 이미지 처럼 
다익 두번 과 간선 지우는 bfs한번만에 해결가능하다.

아래는 해결코드다.

#include<queue>
#include <unordered_map>
#include<vector>
#include<iostream>

using namespace std;

#define cost 0
#define Nextroad 1

// 매직넘버
#define MM_Num  9999999


const auto& mt = make_tuple(MM_Num, MM_Num);

//간선을 확인하며 삭제하는 함수
void Distory(unordered_map<int, vector<tuple<int, int>>>& Umap, vector< queue<int>>& nodeGansun, int end) {
	//도착지점에서 돌아가면서 왔던길 삭제
	while (!nodeGansun[end].empty())
	{
		int num = nodeGansun[end].front();
		nodeGansun[end].pop();
		for (auto& um : Umap[num]) {
			if (get<1>(um) == end) {
				um = make_tuple(MM_Num, MM_Num);
				Distory(Umap, nodeGansun, num);
			}
		}
	}
}
//간선을 기록하며 가는 다익스트라
void find_FIRST_DS(unordered_map<int, vector<tuple<int, int>>>& Umap, int start, int end, int nodesize) {
	priority_queue<tuple<int, int, int>> nextxy;
	vector<int> noodBool(nodesize + 1, MM_Num);
	vector< queue<int>>nodeGansun(nodesize + 1, queue<int>());
	noodBool[start] = MM_Num;

	tuple<int, int, int> nxy;
	int d = 0, arrowRoad = 0, arrowcost = 0;
	nextxy.emplace(make_tuple(0, start, start));

	int first = MM_Num;
	while (!nextxy.empty())
	{
    	

		nxy = nextxy.top();
		nextxy.pop();
		arrowcost = -get<0>(nxy);
		arrowRoad = get<1>(nxy);
        
		if (get<1>(nxy) == end) {
			if (first == get<0>(nxy)) {
				first = get<0>(nxy);
				break;
			}
		}
        //최단거리 이며 다른 간선을 통해 하나의 노드에 도착했을경우
        // 이전의 노드 를 현재 노드에 저장
		if (noodBool[arrowRoad] == MM_Num || noodBool[arrowRoad] > (arrowcost)) {
			noodBool[arrowRoad] = arrowcost;
			nodeGansun[arrowRoad] = queue<int>();
			nodeGansun[arrowRoad].push(get<2>(nxy));
		}
		else if (noodBool[arrowRoad] == (arrowcost))
		{
			nodeGansun[arrowRoad].push(get<2>(nxy));
			continue;
		}
		else  continue;
		d = get<0>(nxy);
		for (int i = 0; i < Umap[get<Nextroad>(nxy)].size(); ++i) {

			tuple<int, int> arrow = Umap[get<1>(nxy)][i];
			arrowRoad = get<1>(arrow);
			arrowcost = get<0>(arrow);
			if (noodBool[arrowRoad] == MM_Num || noodBool[arrowRoad] > (arrowcost + -(d))) {
				nextxy.emplace(make_tuple(-(arrowcost + -(d)), get<1>(arrow), get<1>(nxy)));
			}
		}
	}
	while (!nextxy.empty()) {
		auto b = nextxy.top();
		nextxy.pop();
		if (get<1>(b) == end && get<0>(b) == first) {
			nodeGansun[end].push(get<2>(b));
		}
	}
	Distory(Umap, nodeGansun, end);
	return;
}
//그냥 다익스트라
int find_second_DS(unordered_map<int, vector<tuple<int, int>>>& Umap, int start, int end, int nodesize) {
	priority_queue<tuple< int, int>> nextxy;
	vector<bool> noodBool(nodesize + 1, false);
	tuple<int, int> nxy;
	nextxy.emplace(make_tuple(0, start));
	bool lastnode = false;
	noodBool[start] = true;
    
    //다음 갈 장소가 없으면 끝냄
	while (!nextxy.empty())
	{
		nxy = nextxy.top();
		nextxy.pop();
        온길 기록
		noodBool[get<1>(nxy)] = true;
		//도착지에 도착하면 최단거리 리턴
		if (get<1>(nxy) == end) {
			return  (-get<0>(nxy));
		}
        
		for (const auto& arrow : (Umap[get<1>(nxy)])) {
			//현재 간선에서  갈수있는 간선들 이동
            
            //만약 지워진 간선일경우 
        	if (get<1>(arrow) == MM_Num)continue;
            // 이미 왔던 간선일경우 
			if (noodBool[get<1>(arrow)]) {
				continue;
			}
            // 다음간선 + 이동값 queue 추가
			nextxy.emplace(make_tuple(-(get<0>(arrow) + -(get<0>(nxy))), get<1>(arrow)));
		}
	}
	return (-1);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin.tie(NULL);
    
	int NodeSize = 0, NodeLoadSize = 0, Start = 0, end = 0;
	int node = 0, Xnode = 0, Dis = 0;
	
    unordered_map<int, vector<tuple<int, int>>> Umap;
	vector<int> answer;
	
    while (true)
	{
		cin >> NodeSize >> NodeLoadSize;
		if (NodeSize == 0 && NodeLoadSize == 0)
			break;
		cin >> Start >> end;

		Umap.clear();
		for (int i = 0; i < NodeLoadSize; i++)
		{
			cin >> node >> Xnode >> Dis;
			Umap[node].emplace_back(make_tuple(Dis, Xnode));
		}
		
		find_FIRST_DS(Umap, Start, end, NodeSize);
		answer.emplace_back(find_second_DS(Umap, Start, end, NodeSize));
	}
	for (const auto& an : answer) {
		printf("%d\n", an);
	}
	return 0;
}