[삼성기출] 백준 - C++ 마법사 상어와 비바라기

구현과 시뮬레이션 문제이다. 삼성기출인 '마법사 상어와 블리자드'를 해결했다면, 간단하게 해결할 수 있다.

https://code-block.tistory.com/10 (마법사 상어와 블리자드)

 

풀이

1. 구름 이동

• dx[] = {0, 0, -1, -1, -1, 0, 1, 1, 1}, dy[] = {0, -1, -1, 0, 1, 1, 1, 0, -1} 을 이용하여 '상하좌우 + 대각선'을 표현한다.
• 구름을 이동하고, map의 물 양을 증가한다. 
• visited를 true 로 바꾼다.

2. 대각선 방향의 물 복사

3. 새로운 구름 생성

• vector preList를 선언하여, 새로운 구름이 생성되기 전의 vector cloud를 저장한다.
• preList의 벡터를 반복하며, visited를 false로 바꿔준다.

---

1. Solution 코드

#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;
}

2. 알아야 할 개념

1) C++에서의 cin/scanf

속도향상을 위해서 cin 대신 scanf를 사용한다.

int N;

// cin, cout
cin >> N >> '\n';
cout << N;

// scanf(), printf()
scanf("%d", &N);
printf("%d", N);

 

2) struct Point를 자료형으로 사용하기

• for(Point cur : clouds){ } 이렇게 for문을 사용할 수 있다.
• vector<Point> preList = clouds 이렇게 vector를 선언할 수 있다.

 

3) 초기화에 입력받을 map은 Vector(벡터)가 아니라 Array(배열) 사용하기

// 배열의 원소를 scanf()로 입력받기
for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) 
            scanf("%d", &map[i][j]);
}