[BOJ] (C++) 20057번: 마법사 상어와 토네이도 <Gold 3>

winluck·2024년 1월 10일

C boj

https://www.acmicpc.net/problem/20057

실전에서 구현 문제에 대해 굉장히 약하다는 생각이 들어서, 최근엔 진득하게 구현 문제를 다루고자 한다. 삼성 SW 역량테스트 기출이었던 문제였고, 여러 가지로 얻은 게 많아 정리하려 한다.

문제 설명 및 입출력

문제에서 추출할 수 있는 정보는 다음과 같다.

토네이도 모양으로 움직이며 해당 구역에 존재하는 모래를 분산시킨다.
토네이도는 [1,1] 즉 N*N의 맨 왼쪽 위에 도착하면 소멸한다.
N*N 영역의 바깥으로 밀려난 총 모래 양을 계산한다.
N은 홀수이다. 즉 중심점을 특정할 수 있다.

해결 과정

이 문제는 크게 3가지 틀로 나눌 수 있다.

토네이도의 방향을 바꾸는 부분
실제 토네이도의 영향으로 인해 모래가 퍼지는 것을 구현하는 부분
모래가 N*N 밖으로 나가는 것을 감지하고 이를 계산하는 부분

토네이도 방향 바꾸기

특정 좌표로 토네이도가 이동하는 것이 확정되어 해당 계산을 마치고, 그 특정 좌표로 이동했을 때 자신 주변에 인접한 4가지 칸 중 방문한 칸이 오직 한 칸(즉 직전에 서 있던 부분)일 때 방향을 바꿔주어야 한다.
방향은 그림처럼 좌, 하, 우, 상 순서로 반복되는 규칙을 갖는다.

        // 방향을 꺾어야 하는가? 에 대한 판정
        int cnt = 0;
        for(int i=0; i<4; i++){
            if(!visited[nx + dx[i]][ny + dy[i]]) cnt++;
        }
        if(cnt == 3){
            nowdir = (nowdir+1) % 4;
        }

토네이도 및 정답 계산

첫번째 해결전략

N-N 크기의 배열을 활용하여, 모래가 퍼지는 각 좌표가 N*N 배열을 이탈하는지 여부를 매 움직임마다 판정하고 이탈 시 이를 결과에 더해주고, 그렇지 않으면 해당 칸에 토네이도의 계산을 반영한다.
가장 보편적으로 떠올릴 수 있는 방법이지만, 이론상 약 10개의 if-else 조건문이 매 움직임마다 필요하기에 굉장히 난잡하다고 생각했다.

두번째 해결전략

어차피 가장자리로 토네이도가 움직이는 케이스의 경우, 그 좌표 기준 최대 두 칸 차이밖에 범위가 이탈하지 않는다는 점을 활용한다.
주어진 N*N 배열을 둘러싸는 형태의 [N+4][N+4] 배열을 선언하고, 조건문 없이 토네이도를 구현한다.
마지막에 for문을 통해 N*N 배열 바깥에 존재하는 모래값만 결산한다.
배열 크기가 커지지만, 수많은 if-else문 없이 직관적인 구현이 가능해진다.

나는 2번째 해결전략을 채택하였고, 관련 코드는 아래와 같다.

    for(int i=2; i<=n+1; i++){ // 인덱스 0/1/n+2/n+3은 바깥 껍데기
        for(int j=2; j<=n+1; j++){
            cin >> map[i][j];
            origin[i][j] = 1; // 원래 격자임을 표현
        }
    }
    
    tonado((n+4)/2, (n+4)/2);
    
    for(int i=0; i<=n+3; i++){
        for(int j=0; j<=n+3; j++){
            if(origin[i][j] == 0){ // N*N 외곽 지역
                result += map[i][j]; // 외곽의 모래만을 더해준다.
            }
        }
    }

토네이도 구현

그림의 상황을 그대로 코드로 옮기면 된다. 각 숫자는 %를 의미한다.
참고로, alpha값은 단순하게 다른 비율을 모두 빼고 남은 55%가 아니라, 원래 모래에서 실제 내림 계산을 통해 정수가 된 다른 모든 모래들을 뺀 값이다. 주의하자.

        if(nowdir == 0){ // 좌측 이동
            map[nx][ny-1] += alpha;
            map[nx][ny-2] += five;
            map[nx-1][ny-1] += ten;
            map[nx+1][ny-1] += ten;

            map[nx-1][ny] += seven;
            map[nx+1][ny] += seven;

            map[nx+2][ny] += two;
            map[nx-2][ny] += two;

            map[nx+1][ny+1] += one;
            map[nx-1][ny+1] += one;
        }

소스 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;
int n;
int result = 0;
int nowdir = 0;
int map[505][505]; // 껍데기가 추가된 격자
int origin[505][505]; // 원본 N*N 격자
bool visited[505][505];
int dx[4] = {0, 1, 0, -1}; // 좌하우상 순서로 반복
int dy[4] = {-1, 0, 1, 0};

void tonado(int sx, int sy){
    visited[sx][sy] = true;
    queue<pair<int, int> > q;
    q.push(make_pair(sx, sy));

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        if(x == 2 && y == 2) break; // 종료조건

        int nx = x + dx[nowdir];
        int ny = y + dy[nowdir];
        int val = map[nx][ny]; // 퍼뜨릴 모래
        map[nx][ny] = 0;

        int one = val / 100;
        int two = (val * 2) / 100;
        int five = (val * 5) / 100;
        int seven = (val * 7) / 100;
        int ten = (val * 10) / 100;
        int alpha = val - five - 2*(one + two + seven + ten);
        
        if(nowdir == 0){ // 좌
            map[nx][ny-1] += alpha;
            map[nx][ny-2] += five;
            map[nx-1][ny-1] += ten;
            map[nx+1][ny-1] += ten;

            map[nx-1][ny] += seven;
            map[nx+1][ny] += seven;

            map[nx+2][ny] += two;
            map[nx-2][ny] += two;

            map[nx+1][ny+1] += one;
            map[nx-1][ny+1] += one;
        } else if(nowdir == 1){ // 하
            map[nx+1][ny] += alpha;
            map[nx+2][ny] += five;

            map[nx+1][ny+1] += ten;
            map[nx+1][ny-1] += ten;

            map[nx][ny+1] += seven;
            map[nx][ny-1] += seven;

            map[nx][ny+2] += two;
            map[nx][ny-2] += two;

            map[nx-1][ny-1] += one;
            map[nx-1][ny+1] += one;
        } else if (nowdir == 2){ // 우
            map[nx][ny+1] += alpha;
            map[nx][ny+2] += five;
            map[nx+1][ny+1] += ten;
            map[nx-1][ny+1] += ten;

            map[nx-1][ny-1] += one;
            map[nx+1][ny-1] += one;

            map[nx+1][ny] += seven;
            map[nx-1][ny] += seven;

            map[nx+2][ny] += two;
            map[nx-2][ny] += two;
        } else { // 상
            map[nx-1][ny] += alpha;
            map[nx-2][ny] += five;
            map[nx+1][ny+1] += one;
            map[nx+1][ny-1] += one;

            map[nx][ny+1] += seven;
            map[nx][ny-1] += seven;

            map[nx][ny+2] += two;
            map[nx][ny-2] += two;

            map[nx-1][ny-1] += ten;
            map[nx-1][ny+1] += ten;
        }
        // 방향을 꺾어야 하는가? 에 대한 판정
        int cnt = 0;
        for(int i=0; i<4; i++){
            if(!visited[nx + dx[i]][ny + dy[i]]) cnt++;
        }
        if(cnt == 3){
            nowdir = (nowdir+1) % 4;
        }

		// 토네이도가 다음 좌표로 이동
        q.push(make_pair(nx, ny));
        visited[nx][ny] = true;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    memset(map, 0, sizeof(map));
    memset(origin, 0, sizeof(origin));
    for(int i=2; i<=n+1; i++){
        for(int j=2; j<=n+1; j++){
            cin >> map[i][j];
            origin[i][j] = 1;
        }
    }
    
    tonado((n+4)/2, (n+4)/2);
    
    for(int i=0; i<=n+3; i++){
        for(int j=0; j<=n+3; j++){
            if(origin[i][j] == 0){ // N*N 외곽 지역
                result += map[i][j]; // 바깥으로 밀려난 모래들을 더해줌
            }
        }
    }
    cout << result;
    return 0;
}