문제 소개
BOJ 17144 미세먼지 안녕
썸네일에 나와있듯 골드 5 난이도의 문제이며, solved.ac 기준 CLASS 4 에 수록되어 있는 문제입니다. 복잡한 알고리즘 지식을 그렇게 요하지 않으며 구현만 올바르게 하면 되는 문제입니다.
문제의 상황
- 최소 6 by 6 에서 최대 50 by 50 직사각형 배열이 주어진다는 사실
- 그리고, 1행에만 설치되는 세로로 두칸 차지하는 "공기청정기"가 있고, 나머지 칸들에는 "미세먼지"의 양이 주어진다고 합니다.
- 그리고 다음과 같은 일이 순서대로 일어난다고 합니다.
- 미세먼지의 확산이 일어납니다. 확산되는 양은 현재 칸에 있는 미세먼지 양 / 5 이며, 소수점 이하는 버린다고 합니다. (일반적인 프로그램언어의 int 나눗셈). 공기 청정기가 있거나, 없는칸에는 확산이 일어나지 않습니다.
이는 모든칸에서 동시에 일어납니다. - 먼지의 확산이 끝난 후 공기청정기에서 바람이 나와 미세먼지들을 이동시킵니다. 순환하는 방향은 아래 그림과 같습니다. 먼지는 화살표를 따라 다음 칸으로 가며, 공기청정기에 도착할경우 사라집니다.
- 이러한 조건 속에서 T초후의 방의 미세먼지 잔량을 출력하면 됩니다.
문제의 조건(입력, 제한시간)
방의 세로길이 R, 가로길이 C, 구할 시간 T가 첫줄에 입력으로 주어지고
(, )
그 밑에 줄부터 R개의 줄에 각 방의 상황이 주어집니다. 공기청정기는 -1로 표현되고, 나머지 값은 미세먼지의 양입니다. 공기청정기는 가장 윗행, 아랫행과 적어도 두칸 이상 떨어져 있다고 합니다.
제한시간은 1초, 메모리 제한은 512MB 입니다.
문제를 어떻게 풀 것인가
일단 문제를 처음 보고, 처음에 생각해야 할 것은, 이게 문제의 상황 그대로를 해석해서 풀 수 있는 문제인가(== 시뮬레이션을 하는 문제인가)가 되어야 합니다. 예전에 간단한 시뮬레이션 문제를 풀 때, 문제의 조건을 지키면서 좀더 최적화를 할 수 있는가를 먼저 생각했던 적이 있는데, 일단 PS의 목적은 문제풀이고, 그저 제한사항만 다 지키면 된다 라는 사실을 잊어서는 안되는것 같습니다. 종만책에서도 오랜시간 끙끙 앓으면서 짠 빠르게 돌아가는 코드를 짠 다음 문제를 풀고, 별 생각 안하고 직관적으로 술술 적은 코드를 별 생각없이 제출해봤는데, 그 코드가 맞았습니다를 낼때의 허무함은 이루 말할 수 없으며, 일반적인 PS대회 같은 상황에서는 빠르게 풀 수 있는 문제에 많은 시간을 소비하는것은 시간낭비일 뿐입니다.
각설하고 이 문제의 상황에서 문제 조건을 그대로 시뮬레이션 하는 것으로 메모리, 시간 제한을 어기지 않고 문제를 풀 수 있는지 최악의 상황을 가정해서 생각해 봅시다.
칸의 크기를 으로 하고, 를 1000으로 생각해 봅시다. 공기청정기를 제외한 모든 칸()에 먼지가 모두 있어, 확산연산을 번 만큼 하고, 공기 순환은 개의 칸만큼에 대해서 연산을 해야하니, 대략적으로 계산을 하면 이고, 대략 주먹구구로 1억번 연산을 1초로 잡으니, 문제의 제한시간인 1초안에 분명 풀 수 있습니다.
메모리 크기 제한도 512MB라 넉넉하니, 문제 없을것 같습니다. 따라서 이 문제는 시뮬레이션을 해서 풀 수 있는 문제입니다.
문제를 풀어보자
일단 자세한 사항을 제쳐두고 문제를 푸는 순서를 정해봅시다.
- 입력을 받는다
void getInput() - 먼지 확산을 처리한다
void spread(int r,int c) - 공기 청정기로 인한 공기 순환을 처리한다
void circulate() - 2,3번 과정을 T번 반복한다 (
while등 반복문 이용) - 먼지 총량을 계산하여 출력하고 프로그램을 종료한다.
무척이나 간단한 일이군요. 이제 하나하나 짜봅시다. 물론 문제를 풀어나가면서 처음에 생각했던것 처럼 문제를 쓱쓱하고 풀 수 있는 경우는 잘 없습니다. 지나친 뇌절만 아니라면 생각대로 코드를 망설임 없이 타이핑 해 봅시다.
실제 개발을 할 때에는 전역변수를 함부로 선언하면 안되지만, PS 할 때는, 해당 문제를 풀고 다시 유지보수할 일이 없는 코드이기 때문에, 함수마다 변수 넘겨주는 귀찮은 일을 줄이기 위해서 전역변수를 적극적으로 쓰도록 하겠습니다.
사용할 전역 변수 목록
- 방의 크기를 나타내는 변수 : int R,C
- 반복할 횟수를 나타내는 변수 : int T
- 방의 정보를 저장할 배열 : int room[50][50]
- 공기청정기의 위치를 저장하는 변수 (-1로 초기화) : int cleanerTop
- 방향처리를 쉽게 도와줄 상수 배열들 : const int dy[4], dx[4]
사용할 함수 목록
- 문제를 푸는 순서를 설명하면서 언급한 함수들
- 네모 격자로 구성된 공간 내에서 칸이 유효한지 검증해줄
bool isValidSpace(int r, int c)
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};이렇게 두면 0번 인덱스부터 3번 인덱스까지 각각 위, 오른쪽, 아래, 아래쪽 방향을 의미하게 할 수 있다.
1. 입력 받기
그냥 술술 적어봅시다.
void getInput(){
cin >> R >> C >> T;
for(int i = 0 ; i < R; ++i){
for(int j = 0; j < C; ++j){
int temp;
cin >> temp;
if(cleanerTop == -1 && temp == -1) cleanerTop = i;
room[i][j] = temp;
}
}
}코드 1 : 입력을 받는 함수 void getInput()
다 적었습니다.
2. 먼지 확산을 처리하기
room[r][c]에 있는 먼지를 확산시키는 코드를 작성해보자.
void spread(int r, int c){
//room[r][c]에 있는 먼지를 확산시킨다.
for(int i = 0; i < 4; ++i){//4방향 모두를 확인한다
if(isValid(r+dy[i],c+dx[i])){
... //확산을 처리하는 코드코드 2-1 : 먼지 확산을 처리하는 함수 작성
여기서 확산을 처리할 때, 주의할 점이 있다. 모든 먼지의 확산은 동시에 일어난다고 했는데, 한칸 한칸을 순차적으로 확산을 시키고, 그것을 먼지량 데이터에 바로 반영을 한다면, 확산이 먼저 처리되는 쪽에서 먼지가 다른 칸에 확산되고, 다른 칸은 원래 자기의 먼지의 양만큼 확산을 해야 하는데, 이대로라면 원래 자기의 먼지 + 다른 칸에서 받은 먼지 만큼 다른 칸에 확산을 하게 될 것이다. 이것은 우리가 원하는 바가 아니니, 이를 해결할 방법을 생각해보자.
가장 생각하기 쉬운 방법은. 확산을 진행할 때, 결과를 바로 원래 데이터에 반영하지 않고, 데이터의 변화될 예정량을 저장하는 변수에 그 내용을 저장하여, 모든 칸에 대해 확산될 양을 취합한 후, 그 데이터를 원래 데이터에 반영 시키는 것이다. 그렇게 되면 순차적으로 확산을 처리하지만, 확산되는 양이 원래 자기칸의 먼지만큼에 비례하게 되기 때문에 아까와 같은 문제는 해결된다.
먼지가 확산되어 다른칸에 더해지고, 확산되어 원래 칸에 있는 먼지를 빼는 정보, 즉 확산 후 먼지의 변화량을 저장하는 변수 int room2[50][50]을 만들어서 관리하고, 나중에 room배열에 room2배열의 정보를 반영해야 하니, 정보를 반영하는 함수, void addTwoBoard()도 만듭시다.
사용할 전역 변수 목록
- 방의 크기를 나타내는 변수 : int R,C
- 반복할 횟수를 나타내는 변수 : int T
- 방의 정보를 저장할 배열 : int room[50][50]
- 공기청정기의 위치를 저장하는 변수 (-1로 초기화) : int cleanerTop
- 방향처리를 쉽게 도와줄 상수 배열들 : const int dy[4], dx[4]
- 확산 후 먼지량의 정보를 잠시 저장해둘 배열 : int room2[50][50]
그리고, 확산 계산을 할 때, 매 계산마다 확산되는 양은 달라지고, 이는 이전 확산된 양을 참고해서 쉽게 구할 수 있는 것은 아니므로, room2 배열을 초기화 하는 함수도 하나 만듭시다.
사용할 함수 목록
- 문제를 푸는 순서를 설명하면서 언급한 함수들
- 네모 격자로 구성된 공간 내에서 칸이 유효한지 검증해줄
bool isValidSpace(int r, int c)- room2 배열을 초기화 하는 함수 :
void initRoom2()- room2의 정보를 room[][]에 반영하는 함수 :
void addTwoBoard()
void spread(int r, int c){
//room[r][c]에 있는 먼지를 확산시킨다.
for(int i = 0; i < 4; ++i){//4방향 모두를 확인한다
if(isValid(r+dy[i],c+dx[i])){
room2[r+dy[i]][c+dx[i]] += room[r][c] / 5;
room2[r][c] -= room[r][c] / 5;
}
}
}코드 2-2 : 2-1에 이어서 계속 작성
여기서 쓰인 isValid의 구현도 무척이나 간단합니다.
bool isValid(int r, int c){
if(r < 0 || R <= r || c < 0 || C <= c) return false;//칸을 벗어나면 안됨
if(room[r][c] == -1) return false;//공기청정기가 있는 칸은 확산이 안됨
return true;//그 외에는 확산 가능
}코드 2-3 : isValid의 구현
나머지 함수의 구현은 별거 없습니다. initRoom2()는 반복문 등을 통해서 모두 0으로 초기화하는 코드를 짜면 됩니다.
addTwoBoard도 역시, 반복문을 통해서 사용하는 모든 칸에 대해 room[r][c] += room2[r][c]를 진행하는 코드를 짜면 됩니다.
3. 공기 순환을 처리하기
공기 순환을 처리하는 코드는 문제의 조건대로 짜다보면 난항을 겪을 수 있습니다. 다음 칸에 먼지를 옮겨 놓는건 까지는 좋은데, 그렇다면 다음 칸에 있는 먼지를 그 다음칸에 옮겨야 하는 작업은 어떡할까요? 먼지 정보를 다음 칸에 옮겨버리면, 그 칸에 원래 있던 정보들은 사라지니, 단순히 이를 구현하기는 어렵겠다 라는 생각이 들 것 입니다.
이 문제를 간단히 해결하는 방법은, 공기 순환으로 인한 먼지의 이동을 역순으로 처리하는 것 입니다. 원래 바람은 공기청정기 바로 오른쪽에서 나와서, 윗칸의 경우는 바로 윗칸, 아랫칸의 경우는 바로 아랫칸을 통해, 공기를 순환시키는데, 이 순서를 뒤집에서, 공기청정기의 바로 위, 아래로 부터 출발해서 공기 순환을 처리하자는 것입니다. 그렇게 되면, 원래 순서였다면 맨 마지막에 공기가 닿았을 부분의 먼지가 사라지고(공기청정기 속으로 먼지가 들어가면 사라진다고 문제에 언급되어 있으므로), 그 바로 전의 칸의 먼지를 옮기는데, 아까와는 다르게 기존의 정보를 덧씌우는데 관련해서 문제가 되지 않습니다. 이미 다른데로 옮겨둔 정보거든요.
단 이 방법으로 코드를 작성할 때에는 주의해야할 것이 몇가지가 있습니다.
1. 원래 바람 방향을 기준으로 코드를 짜도 주의할 사항입니다만, 공기청정기 속으로 들어가는 먼지를 따로 처리하거나, 공기청정기의 위치를 저장해 놔서 먼지를 다 옮긴 이후에, 원래 공기청정기가 있는 위치를 복원해 내거나 해야 합니다.
2. 원래 진행 방향으로 먼지를 옮기면, 벽에 부딪힐 때마다, 방향을 꺾으면 됩니다. 하지만, 역방향으로 진행할 때에는, 벽이 없더라도 꺾어야 하는 순간이 있기에, 그 순간들을 잘 처리해 주어야 합니다.
3. 공기 청정기가 위치한 곳에 따라서, 윗쪽에서 나온 바람이 돌아야 하는 코스의 길이와, 아랫쪽에서 나오는 바람이 돌아야 하는 코스의 길이가 다를 수 있습니다.
4. 역순으로 처리하므로, 원래 순서라면 처음에 바람에 날려갈 먼지를 마지막에 따로 처리해 주어야 합니다.
처음에 이 문제를 풀 때, 1번과 관련된 것은 금방 찾아서 해결했지만, 2번에 관한 것을 따로 처리하지 않아서, 코드가 무한루프에 빠져서 디버깅 한다고 많은 시간을 쏟았습니다.
위 사항에 유의하면서 공기 순환에 관련된 코드를 작성해 봅시다.
이차원 좌표를 돌아다닐 예정이니, 위치를 저장하는데에는 pair<int,int>가 제격입니다. first와 second에 row, col을 넣든, x,y좌표를 넣든 해서 위치를 직관적으로 표현할 수 있으니까요.
void circulate(){
bool is1active = true, is2active = true;
//역순으로 진행할 것이니, 위쪽에서 나오는 바람은 위로 가는것이 처음 방향이고
//아랫쪽에서 나오는 바람은 아래로 가는것이 처음 방향일 것
int dir1 = 0, dir2 = 2;
pair<int,int> pos1, pos2;//각각 위에서 나오는 바람, 아래에서 나오는 바람
pos1.first = cleanerTop;
pos2.first = cleanerTop + 1;
pos1.second = pos2.second = 0;
while(is1active || is2active){//두 방향에서 나오는 바람을 다 처리할때까지 반복
//다 돌았으면 비활성화 상태로 되게 설정.
if(pos1.first == cleanerTop && pos1.second == 1) is1active = false;
if(pos2.first == cleanerTop + 1 && pos2.second == 1) is2active = false;
if(is1active && !isValid(pos1.first + dy[dir1], pos1.second + dx[dir1])
|| (pos1.first == cleanerTop && pos1.second == C - 1))
// || 을 기준으로 처음에 검사하는 것은, 현재 방향으로 갔을 때 다음칸이 유효한 칸인지
//두번째는 2.에서 언급한 벽이 없더라도 꺾어야 할 순간을 검사
dir1 = (dir1 + 1) % 4; //방향을 꺾는다
if(is2active && !isValid(pos2.first + dy[dir2], pos2.second + dx[dir2])
|| (pos2.first == cleanerTop + 1 && pos2.second == C - 1))
dir2 = (dir2 + 3) % 4;//방향을 꺾는다
/*dir2는 꺾을때마다 1씩 줄어드는데, -1 % 4는 -1이므로, 이를 따로 처리하기
번거롭기 때문에 3을 더하고 4로 mod 하는 방법을 사용함*/
if(is1active){
// 다음칸에 있는 먼지를 옮긴다.
room[pos1.first][pos1.second] = room[pos1.first + dy[dir1]][pos1.second + dx[dir1]];
pos1.first += dy[dir1]; pos1.second += dx[dir1];//위치 나타내는 pair도 옮긴다.
}
if(is2active){// pos2에 대해서도 위와 같은 작업을 해주자.
room[pos2.first][pos2.second] = room[pos2.first+dy[dir2]][pos2.second+dx[dir2]];
pos2.first += dy[dir2]; pos2.second += dx[dir2];
}
}
//위에서 4.로 언급한 사항
room[pos1.first][pos1.second] = room[pos2.first][pos2.second] = 0;
//위에서 1.로 언급한 사항
room[cleanerTop][0] = room[cleanerTop+1][0] = -1;
}4. 종합하기
이제 문제를 풀기 위해서 작성해야 하는 모든 함수를 작성하였습니다. 이제 이들을 적절한 시기에 부르는 main함수만 짜면 끝입니다.
int main(void){
getInput();
while(T--){
initRoom2();
for(int i = 0; i < R; ++i)
for(int j = 0;j < C; ++j)
if(room[i][j] > 0) spread(i,j);
addTwoBoard();
circulate();
}
cout << getSum();//현재 room 배열에서 먼지의 총량을 계산하는 함수
return 0;
}마치며
크게 어려울 것 없는 구현 문제였습니다만, 문제 풀이의 양이 아직 부족한 탓인지, 문제를 풀면서 몇가지 놓친 부분이 있었던 것 때문에 이거 푸는데 1시간 반 정도 잡아먹었습니다. 앞으로는 더욱 정진해서 이러한 실수를 좀 줄이자 하는 다짐을 품게 해준 고마운 문제인것 같습니다.
끝까지 읽어주셔서 감사합니다.
