[백준/C++] 20057 - 마법사 상어와 토네이도

풀이 시간: 2h30m33s56(문제풀이) + 2h13m41s24(틀린 부분 찾기)

시간 복잡도: O(N^2)

공간 복잡도: O(N^2)

문제

입력

첫째 줄에 격자의 크기 N이 주어진다. 둘째 줄부터 N개의 줄에는 격자의 각 칸에 있는 모래가 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.

출력

격자의 밖으로 나간 모래의 양을 출력한다. 

문제 풀이

헷갈리는 조건 정리

1. α 위치는 현재 진행하는 y방향의 그 다음 방향이다. α = ( cR + dir[cDir][0], cC + dir[cDir][1] )

2. 토네이도가 이동할 때 현재 위치(x), 다음 위치(y) 값의 변화는 없다.

3. α에는 각 위치에서의 비율만큼의 값을 뺀 값이다. 그냥 α 값에다가 현재 위치 값의 55%를 하면 안된다. 소숫점 아래는 모두 버리기 때문에 남은 모래의 값이 정확히 55%가 나오지 않는다.

문제 풀 때 y 위치를 기준으로 확산되는 위치를 계산했다.

초기 코드

#include <iostream>
#include <cmath>
using namespace std;
int N, sand = 0; // 격자 크기, 모래의 양
int cDir = 0; // 좌측 방향부터 시작
int num = 1; // 현재 이동 크기
int A[500][500] = { 0, }; // 격자
int cR, cC; // 현재 위치
int dir[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}}; // 좌하우상 : 토네이도 이동 순서
int diff[4][9][3] = {{ // 확산 방향 : {r, c, %}
        // 좌
        {-1, 1, 1}, {1, 1, 1}, {-2, 0, 2}, 
        {2, 0, 2}, {0, -2, 5}, {-1, 0, 7}, 
        {1, 0, 7}, {-1, 1, 10}, {1, -1, 10}
    }, {
        // 하
        {-1, -1, 1}, {-1, 1, 1}, {0, -2, 2}, 
        {0, 2, 2}, {2, 0, 5}, {0, -1, 7}, 
        {0, 1, 7}, {1, -1, 10}, {1, 1, 10}
    }, {
        // 우
        {-1, -1, 1}, {1, -1, 1}, {-2, 0, 2}, 
        {2, 0, 2}, {0, 2, 5}, {-1, 0, 7}, 
        {1, 0, 7}, {-1, 1, 10}, {1, 1, 10}
    }, {
        // 상
        {1, -1, 1}, {1, 1, 1}, {0, -2, 2}, 
        {0, 2, 2}, {-2, 0, 5}, {0, -1, 7}, 
        {0, 1, 7}, {-1, -1, 10}, {-1, 1, 10}
    }
};

void move() {
    cR += dir[cDir][0]; cC += dir[cDir][1]; // 위치 y로 이동
    int remain = A[cR][cC]; // 남은 모래 양, 일단 현재 위치 y의 값을 저장
    for (int i = 0; i < 9; ++i) {
        // 비율이 새겨진 다음 위치들
        int nR = cR + diff[cDir][i][0];
        int nC = cC + diff[cDir][i][1];
        int value = trunc(A[cR][cC] * diff[cDir][i][2] / 100); // 현재 위치 값 기준 해당 비율만큼의 모래 (소숫점 아래 버림)
        if (nR < 0 || nR >= N || nC < 0 || nC >= N) sand += value; // 격자 밖으로 나간 모래
        else A[nR][nC] += value; // 각 위치 값 갱신
        remain -= value; // 모래 비율만큼의 값을 빼줌
    }
    int aR = cR + dir[cDir][0], aC = cC + dir[cDir][1]; // 위치 α 좌표
    if (aR < 0 || aR >= N || aC < 0 || aC >= N) sand += remain; // 위치 α도 격자 밖으로 나간 경우, 남은 값 모두 밖으로 빼내기
    else A[aR][aC] += remain; // 남은 모래를 위치 α에 더해주기
}

void tornado() {
    cR = cC = N / 2; // 현재 위치 (정가운데)
    while (num < N) { // 이동 크기 num이 N보다 작을 때까지만 이동
        for (int i = 0; i < 2; ++i) { // 이동 크기 2번씩 반복
            for (int j = 0; j < num; ++j) move(); // 한 칸씩 총 num만큼 이동
            cDir = (cDir + 1) % 4; // 이동 방향 변경
        }
        num++; // 이동 크기 1 증가
    }
    // 마지막 최상단 줄 N - 1만큼 이동
    for (int j = 0; j < num - 1; ++j) move(); // 한 칸씩 총 num만큼 이동
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N;
    for (int r = 0; r < N; ++r)
        for (int c = 0; c < N; ++c)
            cin >> A[r][c];
    tornado();
    cout << sand;
    return 0;
}

 

위와 같이 풀었는데 예제 1번 빼고는 답이 다 다르게 나왔다. 뭐가 틀린지 못찾겠어서 참고 코드를 통해 비교해보았다.

 

한 가지 놓친 것이 있는데, 위치 y에 있던 모래가 모두 α로 이동되었으므로 해당 위치 y의 모래를 모두 0으로 만들어줘야 한다. 따라서 move() 함수 마지막에 다음 부분을 추가해주었다.

A[cR][cC] = 0; // y에 있던 모래 모두 α로 이동되었으므로 0

하지만 이렇게 바꾸었음에도 모든 예제의 출력값이 이전 코드와 동일하게 나왔다.

 

PS. 스터디 같이하는 분께서 도와주셔서 찾았다. 🙇🏻‍♀️

보아하니 좌측 방향 10%의 좌표 중 하나를 잘못 옮겨 적었다. {-1, 1, 10} 를 {-1, -1, 10} 로 변경하면 된다.

전체 코드

#include <iostream>
#include <cmath>
using namespace std;
int N, sand = 0; // 격자 크기, 모래의 양
int cDir = 0; // 좌측 방향부터 시작
int num = 1; // 현재 이동 크기
int A[500][500] = { 0, }; // 격자
int cR, cC; // 현재 위치
int dir[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}}; // 좌하우상 : 토네이도 이동 순서
int diff[4][9][3] = {{ // 확산 방향과 비율: {r, c, %}
        // 좌
        {-1, 1, 1}, {1, 1, 1}, {-2, 0, 2}, 
        {2, 0, 2}, {0, -2, 5}, {-1, 0, 7}, 
        {1, 0, 7}, {-1, -1, 10}, {1, -1, 10}
    }, {
        // 하
        {-1, -1, 1}, {-1, 1, 1}, {0, -2, 2}, 
        {0, 2, 2}, {2, 0, 5}, {0, -1, 7}, 
        {0, 1, 7}, {1, -1, 10}, {1, 1, 10}
    }, {
        // 우
        {-1, -1, 1}, {1, -1, 1}, {-2, 0, 2}, 
        {2, 0, 2}, {0, 2, 5}, {-1, 0, 7}, 
        {1, 0, 7}, {-1, 1, 10}, {1, 1, 10}
    }, {
        // 상
        {1, -1, 1}, {1, 1, 1}, {0, -2, 2}, 
        {0, 2, 2}, {-2, 0, 5}, {0, -1, 7}, 
        {0, 1, 7}, {-1, -1, 10}, {-1, 1, 10}
    } 
};

void move() {
    cR += dir[cDir][0]; cC += dir[cDir][1]; // 위치 y로 이동
    int remain = A[cR][cC]; // 남은 모래 양, 일단 현재 위치 y의 값을 저장
    for (int i = 0; i < 9; ++i) {
        // 비율이 새겨진 다음 위치들
        int nR = cR + diff[cDir][i][0];
        int nC = cC + diff[cDir][i][1];
        int value = trunc(A[cR][cC] * diff[cDir][i][2] / 100); // 현재 위치 값 기준 해당 비율만큼의 모래
        if (nR < 0 || nR >= N || nC < 0 || nC >= N) sand += value; // 격자 밖으로 나간 모래
        else A[nR][nC] += value; // // 각 위치 값 갱신
        remain -= value; // 모래 비율만큼의 값을 빼줌
    }
    int aR = cR + dir[cDir][0], aC = cC + dir[cDir][1]; // 위치 α 좌표
    if (aR < 0 || aR >= N || aC < 0 || aC >= N) sand += remain; // 위치 α도 격자 밖으로 나간 경우, 남은 값 모두 밖으로 빼내기
    else A[aR][aC] += remain; // 남은 모래를 위치 α에 더해주기
    A[cR][cC] = 0; // y에 있던 모래 모두 α로 이동되었으므로 0
}

void tornado() {
    cR = cC = N / 2; // 현재 위치 (정가운데)
    while (num < N) { // 이동 크기 num이 N보다 작을 때까지만 이동
        for (int i = 0; i < 2; ++i) { // 이동 크기 2번씩 반복
            for (int j = 0; j < num; ++j) move(); // 한 칸씩 총 num만큼 이동
            cDir = (cDir + 1) % 4; // 이동 방향 변경
        }
        num++; // 이동 크기 1 증가
    }
    // 마지막 최상단 줄 N - 1만큼 이동
    for (int j = 0; j < num - 1; ++j) move(); // 한 칸씩 총 num만큼 이동
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N;
    for (int r = 0; r < N; ++r)
        for (int c = 0; c < N; ++c)
            cin >> A[r][c];
    tornado();
    cout << sand;
    return 0;
}

 

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

20057번: 마법사 상어와 토네이도