[BOJ] 백준 21610 마법사 상어와 비바라기

삼성 SW 코딩 테스트 준비(A형)

삼성 SW 기출 모음

출처: https://www.acmicpc.net/problem/21610

Approach

21년 상반기 1번 문제로 구현 + 시뮬레이션 유형이다.

① 초기에 지정된 4개의 위치에서 구름이 생성된다.

 

② 생성된 구름이 주어지는 방향 d로 s 칸 이동한다.

    이때, 경계선을 벗어나는것 없이 map[][]에서 순환되도록 조건이 있다.

     행/열에 대해서 (N - 1) → (N) → (1) 혹은 (2) → (1) → (N) 구조가 된다.

     이동이 끝나고는 해당 위치에 물을 증가시키고, 구름 위치(visited[][])를 표시한다.

if문과 같이 조건문을 이용해서 처리할 수 있지만

위와 같은 수식을 이용한다면 구름에 도착한 곳을 알 수 있다.

 

해당 계산과정 원리는 아래 글 참고

▶ [ps] 순환되는 행렬 인덱스 (Index) 

[ps] 순환되는 행렬 인덱스 (Index)

 

③ 구름 이동이 끝나고, 물이 존재하는 곳은 인접한 대각선 칸에 물의 개수를  확인해서

    각 map[][]의 물을 증가시킨다. 

    인접하는 영역을 확인할 때는 구름이 이동하는 것과 달리 경계선을 벗어나서는 안된다.

    

④ 현재 구름이 있는 곳을 제외하고, 물이 2 이상인 곳에 새로운 구름을 생성한다. 

    (기존 구름은 제거된다.)

이러한 작업 ② ~ ④을 M번 반복한다.

* Code에 주석을 달아놓았습니다.

* 디버깅할 때는 문제에서 주어진 map[][]을 구현했는지 출력하면 좋습니다.

---

#include <iostream>
#include <vector>
using namespace std;
const int MAX_N = 50;
const int dx[] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
const int dy[] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
struct Node {
    int x, y;
};

int N, M, d, s;
int map[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
vector<Node> clouds;

void input()
{
    // map 크기(N), 이동 명령 횟수(M)
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &map[i][j]);
        }
    }

    // 초기 구름
    clouds.push_back({ N - 1, 0 });
    clouds.push_back({ N - 1, 1 });
    clouds.push_back({ N - 2, 0 });
    clouds.push_back({ N - 2, 1 });
}

void moveClouds(int d, int s) {
    s = s % N;
    for (int c = 0; c < clouds.size(); ++c)
    {
        clouds[c].x = (clouds[c].x + s * dx[d] + N) % N;
        clouds[c].y = (clouds[c].y + s * dy[d] + N) % N;
        map[clouds[c].x][clouds[c].y]++; // 바구니 물 증가
        visited[clouds[c].x][clouds[c].y] = true;
    }
}

void copyWaterMagic(void) {
    for (Node cur : clouds) {
        int wCnt = 0;
        // 인접한 대각선 확인
        for (int k = 2; k <= 8; k += 2) {
            int nextX = cur.x + dx[k];
            int nextY = cur.y + dy[k];
            // 경계선 안에서
            if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N)
                continue;

            // 물이 존재하는 경우
            if (map[nextX][nextY])
                wCnt++;
        }
        map[cur.x][cur.y] += wCnt;
    }
}

void createNewCloud() {
    vector<Node> preList = clouds;
    clouds.clear();
    for (int r = 0; r < N; r++)
    {
        for (int c = 0; c < N; c++)
        {
            // 기존 구름이 있었던 곳이나 물 양이 부족한 경우
            if (visited[r][c] || map[r][c] < 2)
                continue;

            clouds.push_back({ r, c });
            map[r][c] -= 2;
        }
    }

    // 이전 구름이 위치한 곳을 
    for (Node cur : preList)
    {
        visited[cur.x][cur.y] = false;
    }
    preList.clear();

}

int getTotalWater()
{
    int ret = 0;
    for (int r = 0; r < N; r++)
    {
        for (int c = 0; c < N; c++)
        {
            ret += map[r][c];
        }
    }
    return ret;
}

int main(void)
{
    input();
    for (int i = 0; i < M; i++) {
        scanf("%d %d", &d, &s);
        moveClouds(d, s); // d 방향으로 s 만큼 구름 이동
        copyWaterMagic(); // 인접한 대각선 칸에 따른 처리
        createNewCloud(); // 새로운 구름 생성
    }
    printf("%d\n", getTotalWater());
    return 0;
}