문제

문제 링크

해설

• 일반적인 구현 문제입니다만, 골드 상급(난도 중상) 시뮬레이션 문제답게
  문제에서 요구하는 구현 사항이 많습니다.
• 문제의 요구사항들을 1, 2, 3 순서대로 하나씩 적어나가면서 전체적인 프로그램의 기틀을 만든 뒤 각 함수를 만드는 것을 추천드립니다.
• 다행히도, 이 문제에서는 1초 동안 발생하는 일을 순서대로 알려주고 있습니다.
  1. 미세먼지가 4방향으로 확산됩니다.
  2. 공기청정기가 동작합니다. 위쪽은 반시계방향, 아래쪽은 시계방향으로 공기가 순환해 한 칸씩 이동합니다. 미세먼지로 들어가는 먼지는 사라지고, 공기청정기에서 나오는 공기는 미세먼지가 0인 공기입니다.
• 문제의 요구사항에 따라, 전체적인 프로그램의 틀을 만들면 아래와 같습니다.

int main() {
	// 사용자로부터 입력값 받기
	cin >> R >> C >> T
	for (int y = 0; y < R; ++y)
		for (int x = 0; x < C; ++x)
			cin >> arr[y][x];
			// 공기청정기 위치도 파악 후 저장
	
	// T초동안
	while (T--) {
		// 1. 미세먼지 확산 단계
		expandDust();
		
		// 2. 공기청정기 동작 단계
		operateAirPurifier(Up);    // 공기청정기 상단 - 반시계방향
        operateAirPurifier(Down);  // 공기청정기 하단 - 시계방향
	}
	// 남아있는 미세먼지의 양 출력
	int ans = 0;
	for (int y = 0; y < R; ++y)
		for (int x = 0; x < C; ++x)
			ans += arr[y][x];
	cout << ans + 2;	// 공기청정기칸이 각각 -1이므로 2 더해준다.
}

• 위와 같이 전체적인 프로그램의 구조를 만들면, 나머지는 문제조건을 빠트리지 않았는지 주의하면서 함수를 작성하면 됩니다.

주의사항

1. 회전연산

2차원 배열에서의 회전연산은 언제나 까다롭고 햇갈리기 쉽습니다.
회전연산 구현 방법은 대표적으로 두 가지가 있습니다.

1. 회전 대상이 되는 2차원 배열의 겉부분을 따로 1차원 std::vector<int> 지역변수에 저장한 뒤, std::rotate() 함수로 1칸 왼쪽/오른쪽 회전한 뒤 다시 복원하는 방법입니다. 확실히 시간/공간면에서 비용이 크지만, 실수할 가능성은 크게 줄어들기 때문에 시험장에서는 이 방법도 훌륭한 방법입니다.
2. for문을 4개 사용해서 끝점부터 시작점까지 한 칸씩 덮어씌우면서 배열을 회전하는 고전적인 방법입니다. 빠르고 확실하지만, 실수하기도 쉽습니다.

2. 동시성 고려

고난도 시뮬레이션 문제는 언제나 '동시성'으로 우리를 곤란하게 만듭니다. 이 문제도 예외는 아닙니다.

확산 단계에서(0, 0)부터 (R - 1, C - 1)까지 순회하면서 미세먼지가 있는 칸을 찾고 확산을 진행합니다. 이때, 모든 확산은 동시에 발생하기 때문에 이전 칸에서 발생한 확산이 다른 칸의 확산과정에 영향을 줘서는 안 됩니다.

즉, 확산 결과는 지역변수 또는 temp 전역변수에 저장한 뒤 1초의 확산과정이 끝난 뒤 원본 격자판에 붙여넣기 해줘야 동시성 문제를 해결할 수 있습니다.

코드

#include <bits/stdc++.h>
using namespace std;

constexpr int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

int R, C, T, cleaner, answer;
array<array<int, 50>, 50> room;

inline bool isPosCleaner(int y, int x){
	return ((y == cleaner) || (y == cleaner + 1)) && (x == 0);
}

int main() {
	ios::sync_with_stdio(0); cin.tie(nullptr);
	cin >> R >> C >> T;
	for (int y = 0; y < R; ++y) {
		for (int x = 0; x < C; ++x) {
			cin >> room[y][x];
			if (room[y][x] == -1 && cleaner == 0) cleaner = y;
		}
	}
	while (T--){
		// 1. Dust move phase
		array<array<int, 50>, 50> tempRoom;
		copy(begin(room), end(room), begin(tempRoom));
		for (int y = 0; y < R; ++y) {
			for (int x = 0; x < C; ++x) {
				if (isPosCleaner(y, x)) continue;
				int cnt = 0;
				for (const auto& i : d) {
					int ny = y + i[0], nx = x + i[1];
					if (ny < 0 || nx < 0 || ny >= R || nx >= C || isPosCleaner(ny, nx)) continue;
					tempRoom[ny][nx] += floor(room[y][x] / 5);
					cnt++;
				}
				tempRoom[y][x] -= (floor(room[y][x] / 5) * cnt);
			}
		}
		// 2. Air purifier phase
		for (int i = cleaner - 1; i > 0; --i)	tempRoom[i][0] = tempRoom[i - 1][0];
		for (int i = 0; i < C - 1; ++i)			tempRoom[0][i] = tempRoom[0][i + 1];
		for (int i = 0; i < cleaner; ++i)		tempRoom[i][C - 1] = tempRoom[i + 1][C - 1];
		for (int i = C - 1; i > 1; --i)			tempRoom[cleaner][i] = tempRoom[cleaner][i - 1];
		tempRoom[cleaner][1] = 0;
		
		for (int i = cleaner + 2; i < R - 1; ++i)	tempRoom[i][0] = tempRoom[i + 1][0];
		for (int i = 0; i < C - 1; ++i)				tempRoom[R - 1][i] = tempRoom[R - 1][i + 1];
		for (int i = R - 1; i > cleaner + 1; --i)	tempRoom[i][C - 1] = tempRoom[i - 1][C - 1];
		for (int i = C - 1; i > 1; --i)				tempRoom[cleaner + 1][i] = tempRoom[cleaner + 1][i - 1];
		tempRoom[cleaner + 1][1] = 0;
		
		room = std::move(tempRoom);
	}
	for (int y = 0; y < R; ++y)
		for (int x = 0; x < C; ++x)
			answer += room[y][x];
	cout << answer + 2;
}

소스코드 링크

결과