(출처) https://www.acmicpc.net/problem/17144
개요
인풋으로 2차원 배열 형태(row,col)의 맵이 주어지고, 맵의 각 요소들로는 미세먼지의 양을 나타내는 정수가 써져있다.
해당 맵을 가지고 문제에서 정해진 규칙에 맞게 미세먼지의 확산과 공기청정기의 작동을 구현한 뒤 결과물을 출력하면 되는 문제.
시간복잡도에 대해서 먼저 고민해보자면, 들어올 수 있는 row와 col의 최대값이 50 이므로 결국 맵의 최대 크기는 2500칸이다.
미세먼지를 확산을 구현하면서 맵의 2500칸을 전체 탐색하고, 공기청정기를 작동시키면서 또 한번 전체 탐색한다고 치더라도 한 번의 루프에 5000번 정도의 반복탐색이 예상된다.
이 때 최대루프회수(T)가 1000번으로 정해져있으므로 넉넉하게 잡아도 5000 * 1000 = 5백만 정도의 반복이 이 문제에서 다룰 최대치이다.
따라서 시간복잡도는 신경끄고 구현에만 집중하면 될 것 같았다.
구현
구현해야되는 부분은 크게 2가지 파트로 나눠지는데 바로 미세먼지 확산과 공기청정기의 작동의 구현이였다. 두 과정은 순차적으로 일어난다.
첫 번째로 미세먼지의 확산의 구현인데, 먼저 맵을 전체 순회하면서 미세먼지가 존재하는 곳을 찾는다. 미세먼지를 발견했다면, 이 후 정해진 확산 규칙에 맞게 해당 위치의 먼지를 분산시키고 변동된 먼지양을 계산해준다. 이때 주의해야할 것은 먼지가 확산되는 과정을 동시에 처리해줘야 한다는 것이다. 즉 1회의 확산이 진행되고 끝날 때까지 맵에 담겨진 모든 값들이 고정되어야 한다. 순간 순간 확산과정을 map에 업데이트하고, 업데이트된 map의 값으로 다시 확산을 진행하는식으로 하면 오류가 발생한다는 뜻. 따라서 나는 tempMap을 두어서 해당 문제를 해결했다.
두 번째로는 공기청정기의 작동의 구현인데, 공기청정기에서 나오는 바람의 길을 역으로 따라가는 식으로 해당 과정을 구현하였다.
-
바람길 마지막 자리에서 루프 시작
-
이전자리의 미세먼지값을 자신의 값으로 덮어쓰기
-
이전자리의 미세먼지값이 맵의 범위를 벗어난 경우, 탐색의 방향을 변경
-
이전자리의 미세먼지값이 -1인 경우 루프 종료
위와 같은 로직으로 처리해주었다.
코드
#include <vector>
#include <iostream>
using namespace std;
int main() {
//초기화 작업
int r,c,t;
cin >> r >> c >> t;
vector<vector<int>> direction = {{-1,0},{0,1}, {1,0}, {0,-1}}; //상,우,하,좌 순(시계방향)
vector<vector<int>> direction_r = {{1,0},{0,1}, {-1,0}, {0,-1}}; //하,우,상,좌 순(반시계방향)
vector<vector<int>> map(r,vector<int>(c,0));
vector<vector<int>> tempMap(r,vector<int>(c,0));
int machineTop = -1, machineBottom = -1; //공기청정기 윗부분,아랫부분 row 좌표 저장
for(int y = 0; y < r; y++) {
for(int x = 0; x < c; x++) {
int temp;
cin >> temp;
map[y][x] = temp;
tempMap[y][x] = temp;
if(temp == -1) {
if(machineTop == -1) machineTop = y;
else machineBottom = y;
}
}
}
//루프시작
for(int i = 0; i < t; i++) {
tempMap = map;
//미세먼지 확산단계
for(int y = 0; y < r; y++) {
for(int x = 0; x < c; x++) {
if(map[y][x] != 0 || map[y][x] != -1) {
int amount = map[y][x] / 5; // 확산되는 미세먼지 양
int cnt = 0; // 확산횟수
for(int i = 0; i < 4; i++) {
int nextY = y + direction[i][0];
int nextX = x + direction[i][1];
//맵밖으로 나가지는 경우 continue
if((nextX < 0 || nextX >= c) || (nextY < 0 || nextY >= r)) continue;
//공기청정기 좌표인 경우 continue
if(nextX == 0 && (nextY == machineTop || nextY == machineBottom)) continue;
tempMap[nextY][nextX] += amount;
cnt++;
}
tempMap[y][x] -= amount * cnt;
}
}
}
map = tempMap;
//공기청정기 윗부분
int currentY = machineTop - 1, currentX = 0;
int level = 0;
while(true) {
int previousY = currentY + direction[level][0];
int previousX = currentX + direction[level][1];
//방향전환이 필요한 경우
if((previousX < 0 || previousX >= c) || (previousY < 0 || previousY > machineTop)) {
level++;
previousY = currentY + direction[level][0];
previousX = currentX + direction[level][1];
}
if(map[previousY][previousX] != -1) {
map[currentY][currentX] = map[previousY][previousX];
currentX = previousX;
currentY = previousY;
}
//이전칸이 공기청정기인 경우, 모든 칸을 전부 다 옮겼으므로 break
else {
map[currentY][currentX] = 0;
break;
}
}
//공기청정기 아랫부분
currentY = machineBottom + 1, currentX = 0;
level = 0;
while(true){
int previousY = currentY + direction_r[level][0];
int previousX = currentX + direction_r[level][1];
//방향전환이 필요한 경우
if((previousX < 0 || previousX >= c) || (previousY < machineBottom || previousY >= r)) {
level++;
previousY = currentY + direction_r[level][0];
previousX = currentX + direction_r[level][1];
}
if(map[previousY][previousX] != -1) {
map[currentY][currentX] = map[previousY][previousX];
currentX = previousX;
currentY = previousY;
}
//이전칸이 공기청정기인 경우, 모든 칸을 전부 다 옮겼으므로 break
else {
map[currentY][currentX] = 0;
break;
}
}
}
//정답 출력
int result = 0;
for(int y = 0; y < r; y++) {
for(int x = 0; x < c; x++) {
result += map[y][x];
}
}
cout << result + 2 << endl;
return 0;
}