[백준 17144] 미세먼지 안녕!

문제 출처: https://www.acmicpc.net/problem/17144

풀이

어제오늘 합해서 10시간넘게 못풀었던 문제입니다.. 고민했던 시간에 비해 틀린부분이 너무 어렵고 어이없더라구요...삼성..역시 대기업이네요

제가 생각하는 중요한 부분부터 천천히 살펴봅시다.

1.좌표에서 미세먼지가 퍼질 때 ,원본에서 퍼지는 것을 시뮬레이션 하면 안됩니다.

1이상 인 값들이 좌표에 있을 때, 각 값들은 자기자신의 고유의 값을 퍼뜨려야하는데, 원본에서 시뮬레이션을 돌리면 기존의 값들이 수정되어 그 수정된값을 기준으로 퍼뜨리게됩니다. 그게 아니고 원래 자기좌표의 값에서 퍼뜨려야합니다. 즉, 복사본이 필요합니다.

그리고, 주석에도 달아놨는데, 현재자리에서 먼지를 퍼뜨리고 자기자리의 남은 먼지를 계산할때는 원본이아닌 사본을 기준으로 계산해야합니다.

즉, temp[i][j]=map[i][j]-(cnt*val)로 코드작성 시 위의 결과가 나오지않습니다.(예제를 잘 볼 필요가 있습니다.)

2. 맵 복사를 한번하는게 아닙니다.( 문제 잘읽기)

예를들어 t=2일때, t=2일 때 퍼뜨리기+청소연산은 t=1에서 계산한 원본을 사본에 다시 복사해서 계산합니다.(문제만 잘읽으면 됩니다. 제가 실수해서....)

3. 퍼지는 방향을 대충 연산하면 안됩니다. (이거 때문에 10시간.....)

청소기 상단 부, 하단 부에서 회전하며 퍼지는 방향을 그냥 임의의 순서대로 하면안됩니다.

저는 처음에 상단부에서 문제에서 알려준대로 시계방향(오른쪽->위->왼쪽->아래 순), 하단부는 반시계방향(오른쪽->아래->왼쪽->위)로 계산했습니다.

당연하게 생각했고, 여기서 틀린것을 눈치못챘는데, 직접 그려보면, 위처럼 코드작성시, 회전하지않고 좌표밖으로 빠져나가는 숫자들이 생깁니다. 

저처럼 코드를 작성하신분들은 위의 그림(청정기상단부분)에 본인의 식을 직접 대입하며 그려보면 실수임을 할 수 있습니다.

이것을 해결하려면, 공기청정기로 빨려들어가는 부분부터 역순으로 계산하는게 편합니다.

이게 당연한건지는 모르겠는데 이렇게 해야 정확한 연산이 되더라구요. 그리고, 공기청정기 윗부분, 아랫부분의 x좌표+1자리는 따로 0으로 체크해줘야합니다.

즉, 공기청정기에서 불어오는 바람은 따로 0으로 체크해줘야합니다.따로 체크를 해주지않고 방향계산 때 같이 한번에 계산해버리면 공기청정기 자리가 -1이아닌 0으로 바껴버리는 경우가 생깁니다. 

그리고 방향회전 연산 시 잔실수가 나올수 있는 가능성이 높기 때문에 코드를 꼼꼼하게 작성할 필요가 있습니다.

4. 공기청정기의 위치를 pair에 저장할 때 저처럼 이런 잔실수를 하지않기를바랍니다.. (실수한 부분이라 적어둡니다.)

위의 설명들을 총 망라해서 코드로 작성하면 다음과 같습니다.

코드

#include<iostream>
using namespace std;
int map[50][50];
int temp[50][50];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
pair<int, int>p[2];
int r, c, t, ans;
void spread();
void clean_room();
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	int index = 0;
	cin >> r >> c >> t;
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == -1) {
				p[index].first = i;
				p[index].second = j;
				index++;
			}
		}
	}

	
	//퍼뜨리고 청소하기
	for (int i = 0; i < t; i++)
	{
		spread();
		clean_room();
	}

	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			if (map[i][j] >= 1)
				ans += map[i][j];
		}
	}
	cout << ans << '\n';

}
void spread()
{
	//복사 
	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
			temp[i][j] = map[i][j];
	
	int cnt, val, ny, nx;
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			cnt = 0;
			if (map[i][j] != -1 && map[i][j] != 0)
			{
				//temp[i][j]/5하면안됨. 이미 수정되있을수도있는값이므로.
				val = map[i][j] / 5;
				for (int k = 0; k < 4; k++)
				{
					ny = i + dy[k];
					nx = j + dx[k];
					if (ny >= 0 && nx >= 0 && ny < r && nx < c && map[ny][nx] != -1)
					{
						//누적된값을 계속더해감
						temp[ny][nx] = temp[ny][nx] + val;
						cnt++;
					}
				}
				//현재좌표에누적된값에서 빼야되므로 원본map[i][j]에서 빼면안됨!!
				temp[i][j] = temp[i][j] - (cnt * val);
			}
		}
	}
	//원본에 다시 삽입
	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
			map[i][j] = temp[i][j];
}
void clean_room()
{
	//p[0].first=2,p[0].second=0;
	//청정기 윗부분,아랫부분에 대해
	//주의 : 빨아들여지는 부분부터 역순으로 방향잡아야됨

	for (int i = 0; i < 2; i++)
	{
		//윗부분
		if (i == 0)
		{
			//왼쪽
			for (int i = p[0].first-1; i > 0; i--)
				map[i][0] = map[i-1][0];
			//위쪽
			for (int i = 1; i < c; i++)
				map[0][i - 1] = map[0][i];
			//오른쪽
			for (int i = 1; i <= p[0].first; i++)
				map[i - 1][c - 1] = map[i][c - 1];
			//아래
			for (int i = c - 1; i > 1; i--)
				map[p[0].first][i] = map[p[0].first][i - 1];

				//청소기에서 오는 바람(0) 처리해주기
				map[p[0].first][1] = 0;
				
		}
		//p[1].first=3, p[1].second=0;
		//아래방향
		else if (i == 1)
		{
			//왼쪽
			for (int i = p[1].first + 1; i < r - 1; i++)
				map[i][0] = map[i + 1][0];
			//아래쪽
			for (int i = 1; i < c; i++)
				map[r - 1][i - 1] = map[r - 1][i];
			//오른쪽
			for (int i = r - 1; i >=p[1].first+1; i--)
				map[i][c - 1] = map[i - 1][c - 1];
			//위
			for (int i = c - 1; i > 1; i--)
				map[p[1].first][i] = map[p[1].first][i - 1];
			//청소기에서 오는바람 0처리
			map[p[1].first][1] = 0;
		}
	}
}

결과