2382.미생물격리

이번에 풀어볼 문제는 SW Expert의 미생물 격리이다. 정답률은 50%이지만

생각보다 난이도는 높지않다. 하지만 역시나 잘못된 설계 혹은 착각하면 일부분만 자꾸 맞는 이상한 늪에 빠진다..

때문에 푸는방법이 정확하고 설계도 정확했지만 시간이 생각보다 오래걸렸다..(눈아프다..)

SW Expert Academy

 

 

---

 

문제를 푸는 설계는 간단하다. 크게 3가지를 구현해주면된다.

 

1. 미생물의 방향 이동 구현

2. 미생물이 반감 및 방향이 전환되는 부분 구현

3. 미생물이 합쳐지고 그 중 가장 미생물의 개수가 많은 방향을 따라 움직이도록 하는 부분 구현

 

이 문제를 풀때의 포인트는 2차원 map배열이 아닌 deque에 넣은 cnt로 남은 미생물의 개수를 판단하는 것이고

deque의 cnt값이 0가 되면 탐색을 pass하는 것도 이용해주면 좋다.

map 2차원 배열은 겹쳐지는 부분에서 크기를 판단하는 부분으로만 이용되었다.

 

이 문제를 풀면서 주의해야할 점은 바로 3번인데 이러한 형태를 착각하면 말그대로 조진다.. 

우리가 진행해야하는 것은 다음과 같은 예시에서 2,3,4의 크기 중 가장 큰 미생물의 방향을 따르도록 구현해야하는데

생각보다 위의 형태의 실수를 많이 한다 => 해당 값을 누적하는 건 맞는데 누적 시킨채로 비교를 하는 것이다.

이런 형태의 구현을 진행할 때 정신 똑바로 차려야한다. 그렇지 않으면 틀린 것을 발견하기 어렵다

(심리상 이 부분을 절대로 틀렸다고 생각하지 않게 될 수 있기 때문이다.)

 

---

 

 

#pragma warning(disable:4996)
#include <iostream>
#include <deque>
#include <string.h>
 
#define MAX 101
 
using namespace std; 
 
int T, N, M, K;
 
struct cell{
    int x, y, cnt, dir;
};
 
int dx[5] = { 0, -1, 1, 0, 0 };
int dy[5] = { 0, 0, 0, -1, 1 };
 
deque<cell> c;
 
int map[MAX][MAX]; // 겹치는 구간에 사용되는 배열
int check[MAX][MAX]; // cell의 인덱스가 저장되는 배열
 
int ans;
 
void init(){
    ans = 0;
    memset(check, 0, sizeof(check));
    memset(map, 0, sizeof(map));
    c.clear();
}
 
void search(){
    int x, y, dir, cnt;
    for (int t = 0; t < M; t++){
        for (int i = 0; i < c.size(); i++){
 
            if (c[i].cnt==0) // 미생물의 갯수가 0인 경우 탐색 pass
                continue;
 
            x = c[i].x;
            y = c[i].y;
            dir = c[i].dir;
            cnt = c[i].cnt;
 
            if (x + dx[dir] == 0 || x + dx[dir] == N - 1 || y + dy[dir] == 0 || y + dy[dir] == N - 1){ // 박멸이라면
                c[i].cnt /= 2; // 미생물의 양 반감
                c[i].x += dx[dir]; // 좌표 이동
                c[i].y += dy[dir]; // 좌표 이동
                check[c[i].x][c[i].y] = i+1; // 옮겨진 check 배열에 idx 저장(idx가 0일수 있으므로 +1 하고 나중에 빼주는 방식을 이용)
 
                if (c[i].dir == 1) // 방향 반대로 전환
                    c[i].dir = 2;
                else if (c[i].dir == 2)
                    c[i].dir = 1;
                else if (c[i].dir == 3)
                    c[i].dir = 4;
                else if (c[i].dir == 4)
                    c[i].dir = 3;
 
            }
            else if (check[x + dx[dir]][y + dy[dir]]){ // 어떠한 미생물이 이동하려는 좌표에 이미 존재할 때
 
                if (map[x + dx[dir]][y + dy[dir]] < c[i].cnt){ // 기존의 값보다 새로 이동해오는 값이 더 크다면
                    map[x + dx[dir]][y + dy[dir]] = c[i].cnt; // 새로 이동해오는 값을 map에 저장
                    c[check[x + dx[dir]][y + dy[dir]] - 1].dir = dir; // 새로 이동해오는 방향으로 바꿈
                }
 
                c[check[x + dx[dir]][y + dy[dir]] - 1].cnt += c[i].cnt; // 이미 존재하는 idx - 1의 cell의 cnt에 더해줌
                c[i].cnt = 0; // 합쳐졌기때문에 해당 미생물의 숫자는 0
 
            }
            else if (!check[x+dx[dir]][y+dy[dir]]){ // 이동하려는 좌표에 어떠한 미생물도 존재하지 않을 때
                check[x + dx[dir]][y + dy[dir]] = i+1; // 옮겨진 check 배열에 idx 저장(idx가 0일수 있으므로 +1 하고 나중에 빼주는 방식을 이용)
                c[i].x += dx[dir]; // 좌표 이동
                c[i].y += dy[dir]; // 좌표 이동
                map[c[i].x][c[i].y] = c[i].cnt; // 이동 후의 좌표값에 미생물 개수 저장
            }
        }
        memset(check, 0, sizeof(check)); // idx값들 초기화
    }
 
    for (int i = 0; i < K; i++) // deque에 저장된 갯수들만 더하자
        ans += c[i].cnt;
 
}
int main() {
    freopen("2382.txt", "r", stdin);
    cin >> T;
    for (int z = 1; z <= T; z++){
        init();
        cin >> N >> M >> K;
        int x, y, cnt, dir;
        for (int i = 0; i < K; i++){
            cin >> x >> y >> cnt >> dir;
            c.push_back({ x, y, cnt, dir });
        }
 
        search();
        cout << "#" << z << " " << ans << "\n";
    }
    return 0;
}

 

 

 

 

 

이런 문제는 간단하게 풀 수 있어야 했는데..

실수하니까 겉잡을 수 없다.. 허허허..

어려운 문제를 푸는 것보다 풀 수 있는 문제에서

실수한걸 찾는 것이 더 골치아픈것 같다.