[SW Expert Academy] 2382. 미생물 격리

2382. [모의 SW 역량테스트] 미생물 격리

삼성 SW Expert Academy의 문제들은 저작권이 걸려있기 때문에 링크로 대체하겠습니다!

클릭시 이동합니다!

어떻게 풀까?

시뮬레이션 문제입니다.

문제가 요구하는 사항을 구현하는 것이 가장 주가됩니다!

풀기 위해 생각해봐야 할 것이 몇 군 데 있습니다.

1. 시간에 따른 미생물의 이동 (가장 기본)

- 각 미생물 군집에 따라 미생물들의 수와 이동 방향이 주어집니다.

- 미생물들은 매 시간마다 자신의 이동 방향으로 한 칸 이동합니다.

2. 끝에 닿았을 경우의 처리

- 이동하는 방향을 반대로 해야한다.

- 미생물의 수가 절반으로 줄어야한다.

단, 미생물의 수가 홀 수 였다면, 소수점 이하를 버린다.

미생물 수가 0이 되면 군집이 사라진다.

3. 여러 미생물이 만났을 경우의 처리

- 여러 미생물이 만나면, 미생물의 합은 만난 미생물들의 합 값이다.

예로, 미생물이 1마리, 3마리, 5마리가 맵의 한 장소에서 만나면 9가 된다.

- 여러 미생물 군집이 만났을 경우, 합쳐진 군집의 이동 방향은 만난 미생물 군집들 중에서 가장 많은 수가 많았던 미생물 군집의 이 

  동방향이다.

우선, 1번을 해결하기 위해 구조체를 만듭시다!

미생물 구조체는

{

미생물의 이동방향

미생물의 현재 위치 ( r, c )

미생물의 수

}

세 가지의 정보가 있으면 될 것 입니다!

이 미생물 군집은 이제 1번 부터 n번 까지 번호를 붙여서 관리합니다!

참고로, 미생물의 수가 0이라는 것은 해당 군집이 사라졌다는 것을 의미합니다!

2번은 어떻게 해결하면 좋을까요?

경계라는 것은, 행과 열이 0이거나 n-1인 경우입니다.

그럼, 미생물이 이동했을때마다 이동한 위치가 경계쪽인지를 알 기 위한 isOut(r, c)를 만들어 놓으면 좋겠군요!

이동 방향은 반대가 됩니다!

상 1 하 2 좌 3 우 4 입니다.

쉽게 변경하기 위해서는

conv[5]라는 배열을 만들어서 

상 -> 하가 되야하기 때문에 conv[1] = 2를 넣고,

하 -> 상이 되야하기 때문에 conv[2] = 1,

좌 -> 우를 위해 conv[3] = 4,

우 -> 좌를 위해 conv[4] = 3을 넣읍시다!

그럼 이제 미생물의 이동방향 = conv[미생물의 현재 이동방향] 을 통해서 변경할 수 있습니다! 워후!

경계에서 미생물은 반으로 나눠지고, 소수는 버리기 때문에, 짝수든, 홀수든 상관하지 않고 그냥 나누기 2를 해버리면 됩니다!

미생물 군집의 미생물 수 = 현재 미생물 군집의 수 / 2

0이 되면 군집이 사라진다는 것을 잊지맙시다.

이제 가장 어려운 3번 입니다!

저는 3번을 정리하기 위해 n*n 맵 2개를 사용했습니다!

n*n에는 현재 (r,c)에 있는 미생물의 대표를 넣어놓는 맵 하나와, 

미생물의 방향을 결정짓는 중요한 요소인 미생물의 수를 저장하는 맵 하나를 사용했습니다!

이렇게 하면, 미생물이 이동 했을 때, 해당 위치에 있는 미생물의 대표를 설정할 수 있습니다!

과정은,

1. 이동 하기 전에 해당 좌표를 대표하는 미생물이 있는지 확인한다. (있으면 3번부터)

2. 없으면, 해당 좌표를 대표하는 미생물은 자신이 된다!, 방향 결정 군집 미생물의 수에도 자신의 미생물 수를 넣는다.

3. 있다면, 자신의 미생물을 해당 좌표를 대표하는 미생물에게 더해준다! (미생물 수 최신화)

4. 또한, 방향을 바꾸기 위해 현재 방향을 결정짓는 군집 미생물의 수를 비교한다.

- 만약, 자신의 미생물 수가 방향 결정 군집 미생물 수보다 크면, 해당 좌표의 방향 결정 군집 미생물 수를 자신으로 바꾸고, 

  해당 좌표를 대표하는 미생물 군집의 방향을 자신의 방향으로 바뀐다.

- 작다면, 무시한다.

5. 모든 처리가 끝났으면, 이제 해당 미생물 군집은 필요가 없다! 자신의 미생물 군집의 수를 0으로 만든다. 

 

예를 들어서 설명해 드리겠습니다!

자 처음에는 이렇게 해당 좌표를 대표하는 미생물의 번호와 방향 결정 군집 미생물의 수는 비어 있습니다.

맵의 상태는 위와 같습니다.

미생물 군집 번호가 작은 것 부터 움직입시다! 1번 미생물 군집이 우선 위로 향할 것입니다. (3,3)으로 이동하겠죠!

그런데, 아직 해당 좌표를 대표하는 미생물의 번호는 없기 때문에, 해당 좌표를 대표하는 미생물의 번호를 1로 하고, 방향을 결정하는 미생물 군집의 수를 자신의 미생물 수인 2로 세팅합니다.

이제 위 상태에서 2번 군집을 오른쪽으로 이동해봅시다!

앗, (3,3)으로 이동해야하는데, 이미 해당 좌표를 대표하는 미생물이 있습니다!

현재 1번의 방향을 결정하는 군집의 미생물 수가 2입니다! 현재 2번 군집의 미생물의 수는 10개이므로, 방향을 결정하는 미생물의 군집이 바뀝니다! 즉, 현재 2번 미생물 군집이 향하는 방향이 오른쪽이기 때문에, (3,3)을 대표하는 1번 미생물 군집의 방향을 오른쪽으로 바꿉니다!

그리고, 자신의 미생물들을 (3,3)을 대표하는 1번 미생물 군집으로 옮겼으므로, 2번 미생물 군집의 미생물들의 수는 0으로 바꿔줍니다.

이렇게 하면, 2번 미생물 군집은 사라지게 됩니다.

이제 3번 미생물 군집을 이동시킵시다! 여전히 (3,3)을 대표하는 미생물의 군집이 있습니다!

따라서, (3,3)을 대표하는 군집의 미생물들에 자신이 가진 미생물들의 수를 더합시다!

아쉽게도, 방향을 결정하는 군집 미생물의 수는 10보다 작기 때문에 방향을 바꿀 수는 없겠군요!

결과 입니다!

이렇게 구조체와 2 차원 맵 2개를 이용해서 미생물의 처리를 보다 간편하게 할 수 있습니다!

나머지는, 주어진 시간만큼 시뮬레이션을 진행하고, 마지막에 미생물들의 수들을 모두 더해서 출력해주면 됩니다!

코드

#include<cstdio>
#include<cstring>
int n, m, k;
int info[100][100][2];
 
//미생물 정보
struct infos {
    int direct; // 방향 1 : 상 2 : 하 3 : 좌 4 : 우
    int num;    // 미생물 개수
    int cod[2];    // 미생물 좌표
} sangs[1001];
 
int dr[5] = { 0, -1, 1, 0,0 };    // 상하좌우
int dc[5] = { 0,0,0,-1,1 };        // 상하좌우
int conv[5] = { 0, 2,1,4,3 };    // 상 -> 하, 하 -> 상, 좌 -> 우, 우 -> 좌
 
// 행, 열이 0 이거나 n-1이면 경계로 간다!
bool isOut(int r, int c) {
    return r == 0 || r == n - 1 || c == 0 || c == n - 1;
}
 
int main() {
    int t;
    scanf("%d\n", &t);
 
    for (int tc = 1; tc <= t; tc++) {
        scanf("%d %d %d\n", &n, &m, &k);
 
        //미생물 정보 받기
        for (int i = 1; i <= k; i++) {
            scanf("%d %d %d %d\n", &sangs[i].cod[0], &sangs[i].cod[1], &sangs[i].num, &sangs[i].direct);
        }
 
        //시간만큼 시뮬레이션 진행
        while (m--) {
            //맵을 초기화 한다!
            memset(info, 0, sizeof(info));
 
            for (int i = 1; i <= k; i++) {
                infos &m = sangs[i];
 
                // 미생물 수가 0이면, 사라진 미생물 군집
                if (m.num == 0) continue;
 
                // 이동 방향으로 이동한다.
                m.cod[0] += dr[m.direct];
                m.cod[1] += dc[m.direct];
                
                // 경계에 닿았을 경우 방향을 반대로 바꾸고, 미생물 수를 반으로 줄인다.
                if (isOut(m.cod[0], m.cod[1])) {
                    m.direct = conv[m.direct];
                    m.num >>= 1;
                }
 
                //이미 해당 좌표를 대표하는 미생물이 있는 경우
                if (info[m.cod[0]][m.cod[1]][0]) {
                    
                    // 해당 좌표를 대표하는 미생물 군집의 번호를 받는다.
                    int idx = info[m.cod[0]][m.cod[1]][0];
 
                    //대표 미생물 군집에 자신의 미생물 수를 더한다.
                    sangs[idx].num += m.num;
 
                    //만약, 방향을 대표하는 미생물 군집의 미생물 수보다 자신의 미생물 수가 많다면 미생물 군집의 방향을 자신의 방향으로 
                    //바꾸고, 방향을 대표하는 미생물 군집의 수를 자신의 미생물 수로 바꾼다!
                    if (info[m.cod[0]][m.cod[1]][1] < m.num) {
                        info[m.cod[0]][m.cod[1]][1] = m.num;
                        sangs[idx].direct = m.direct;
                    }
 
                    //처리가 완료되면 자신의 미생물 군집을 사라지게 한다.
                    m.num = 0;
                }
 
                //해당 좌표를 대표하는 미생물 군집이 없으면 자신이 해당 좌표를 대표하는 미생물 군집이 된다.
                else {
                
                    info[m.cod[0]][m.cod[1]][0] = i;
                    info[m.cod[0]][m.cod[1]][1] = m.num;
                }
            }
        }
        int res = 0;
        // 살아있는 미생물들의 수를 출력한다.
        for (int i = 1; i <= k; i++) res += sangs[i].num;
        printf("#%d %d\n", tc, res);
    }
}
 
 
 

여담

알아보기 쉽게 하기 위해 코드에 주석을 열심히 달았습니다!

시간 복잡도는 주어진 시간동안 미생물의 수 만큼 반복하기 때문에, O(MN) 입니다.