728x90
반응형
https://www.acmicpc.net/problem/20057
20057번: 마법사 상어와 토네이도
마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을
www.acmicpc.net
최종 코드
GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음
백준 알고리즘 소스 코드 모음. Contribute to hwayeon351/BEAKJOON-Algorithms development by creating an account on GitHub.
github.com
//
// main.cpp
// BJ20057_1
//
// Created by Hwayeon on 2021/10/18.
//
#include <iostream>
using namespace std;
int N;
int A[500][500] = {0, };
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int spread[4][10][3] = {
//0-좌
{{0,-2,2}, {-1,-1,10}, {0,-1,7}, {1,-1,1}, {-2,0,5}, {-1,1,10}, {0,1,7}, {1,1,1}, {0,2,2}, {-1, 0, 0}},
//1-하
{{-1,-1,1}, {1,-1,1}, {-2,0,2}, {-1,0,7}, {1,0,7}, {2,0,2}, {-1,1,10}, {1,1,10}, {0,2,5}, {0,1,0}},
//2-우
{{0,-2,2}, {-1,-1,1}, {0,-1,7}, {1,-1,10}, {2,0,5}, {-1,1,1}, {0,1,7}, {1,1,10}, {0,2,2}, {1,0,0}},
//3-상
{{0,-2,5}, {-1,-1,10}, {1,-1,10}, {-2,0,2}, {-1,0,7}, {1,0,7}, {2,0,2}, {-1,1,1}, {1,1,1}, {0,-1,0}}
};
int tx, ty;
int gone = 0;
void spread_sand(int tx, int ty, int d){
int ay = A[ty][tx];
int total_spread = 0;
A[ty][tx] = 0;
int x, y, p, sand;
for(int i=0; i<9; i++){
x = tx + spread[d][i][0];
y = ty + spread[d][i][1];
p = spread[d][i][2];
sand = ay*(0.01*p);
if(x<0 || x>=N || y<0 || y>=N) gone += sand;
else A[y][x] += sand;
total_spread += sand;
}
x = tx + spread[d][9][0];
y = ty + spread[d][9][1];
if(x<0 || x>=N || y<0 || y>=N) gone += (ay-total_spread);
else A[y][x] += (ay-total_spread);
}
void move_tornado(){
int d = 0;
for(int dis=1; dis<=N; dis++){
int ndis = dis;
for(int i=0; i<2; i++){
if(dis == N) ndis = N-1;
for(int j=0; j<ndis; j++){
tx += dx[d];
ty += dy[d];
spread_sand(tx, ty, d);
}
if(dis == N) return;
d = (d+1)%4;
}
}
}
int main(int argc, const char * argv[]) {
cin >> N;
for(int y=0; y<N; y++){
for(int x=0; x<N; x++){
cin >> A[y][x];
}
}
tx = N/2;
ty = N/2;
move_tornado();
cout << gone << endl;
return 0;
}풀이 과정
풀이 시간 1시간 11분
//
// main.cpp
// BJ20057_1
//
// Created by Hwayeon on 2021/10/18.
//
#include <iostream>
using namespace std;
int N;
//A[r][c] = (r, c)에 있는 모래의 양
int A[500][500] = {0, };
//0-좌, 1-하, 2-우, 3-상
//토네이도 이동 방향이 좌->하->우->상으로 반복된다
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
//spread[d][i] = {xx, yy, p}
//d 방향으로 토네이도가 이동하여 흩어진 모래가 이동할 칸과 비율 정보
//토네이도 = (tx, ty)일 때, (tx+xx, ty+yy)칸에 p%의 모래가 도착한다
int spread[4][10][3] = {
//0-좌
{{0,-2,2}, {-1,-1,10}, {0,-1,7}, {1,-1,1}, {-2,0,5}, {-1,1,10}, {0,1,7}, {1,1,1}, {0,2,2}, {-1, 0, 0}},
//1-하
{{-1,-1,1}, {1,-1,1}, {-2,0,2}, {-1,0,7}, {1,0,7}, {2,0,2}, {-1,1,10}, {1,1,10}, {0,2,5}, {0,1,0}},
//2-우
{{0,-2,2}, {-1,-1,1}, {0,-1,7}, {1,-1,10}, {2,0,5}, {-1,1,1}, {0,1,7}, {1,1,10}, {0,2,2}, {1,0,0}},
//3-상
{{0,-2,5}, {-1,-1,10}, {1,-1,10}, {-2,0,2}, {-1,0,7}, {1,0,7}, {2,0,2}, {-1,1,1}, {1,1,1}, {0,-1,0}}
};
//토네이도의 현재 위치
int tx, ty;
//격자 밖으로 나간 모래의 양
int gone = 0;
void spread_sand(int tx, int ty, int d){
//y 칸의 모래의 양
int ay = A[ty][tx];
//흩날려진 모래의 양
int total_spread = 0;
//토네이도가 y칸으로 이동했으므로 y칸의 모래는 0으로 바꿔준다
A[ty][tx] = 0;
//비율이 적힌 9개의 칸에 모래를 흩날린다
int x, y, p, sand;
for(int i=0; i<9; i++){
//모래가 도착하는 칸
x = tx + spread[d][i][0];
y = ty + spread[d][i][1];
//모래의 비율과 양
p = spread[d][i][2];
sand = ay*(0.01*p);
//모래가 격자 밖으로 흩날리는 경우, gone에 모래의 양을 더한다
if(x<0 || x>=N || y<0 || y>=N) gone += sand;
//모래가 도착하는 칸에 흩날린 모래 양을 더한다
else A[y][x] += sand;
//흩날려진 모래의 양을 카운팅
total_spread += sand;
}
//알파 칸의 위치
x = tx + spread[d][9][0];
y = ty + spread[d][9][1];
//격자를 벗어나는 경우, gone에 모래의 양을 더한다
if(x<0 || x>=N || y<0 || y>=N) gone += (ay-total_spread);
//알파 칸에 나머지 모래를 더한다
else A[y][x] += (ay-total_spread);
}
void move_tornado(){
//처음 토네이도의 이동 방향은 0-좌
int d = 0;
//dis = d방향으로 이동하는 거리
//1,1,2,2,3,3,4,4,...,N-1,N-1,N-1의 규칙을 가지고 이동거리가 변한다
for(int dis=1; dis<=N; dis++){
int ndis = dis;
//dis에 대해 이동방향을 바꾸어 2번 이동한다
for(int i=0; i<2; i++){
//마지막 맨 윗행의 경우만 예외적으로 N-1 이동
if(dis == N) ndis = N-1;
for(int j=0; j<ndis; j++){
//토네이도 d방향으로 한 칸 이동
tx += dx[d];
ty += dy[d];
//모래 흩날리기 -> O(1)
spread_sand(tx, ty, d);
}
//마지막 칸으로 이동한 경우, 함수 종료
if(dis == N) return;
//방향 바꾸기
d = (d+1)%4;
}
}
}
int main(int argc, const char * argv[]) {
cin >> N;
for(int y=0; y<N; y++){
for(int x=0; x<N; x++){
cin >> A[y][x];
}
}
//토네이도 처음 위치 초기화
tx = N/2;
ty = N/2;
//토네이도 이동 시작 -> O(N^2)
move_tornado();
cout << gone << endl;
return 0;
}
//시간복잡도 = O(N^2), 공간복잡도 = O(N^2)이전 풀이
풀이 시간 2시간 46분
모래를 흩뿌리는 부분에서 4방향의 경우를 모두 나누어 각 칸에 흩뿌리도록 노가다로 구현했다...
각 경우에 따라 잘 흩뿌려지고 있는지를 확인하는 디버깅 과정에서 시간을 진짜 많이 소요했다...
그래도 3시간 안에 풀 수 있어서 다행이지만, 다음에는 흩뿌리는 과정을 간단한 로직으로 짜보도록 해야겠다.
#include <iostream>
using namespace std;
int N;
int board[500][500] = {0, };
//토네이도의 이동은 좌->하->우->상 방향으로 바뀌기 때문에 순서를 고려한다
int dc[4] = {-1, 0, 1, 0};
int dr[4] = {0, 1, 0, -1};
//격자 밖으로 나간 모래의 양을 담는 변수
long long total_out = 0;
void spread_sand(int r, int c, int d){
int sum = 0;
int per = 0;
int out = 0;
int y = board[r][c];
switch (d) {
//왼쪽
case 0:
per = y*0.02;
if(r-2 >= 0){
board[r-2][c] += per;
sum += per;
}
else out += per;
if(r+2 < N) {
board[r+2][c] += per;
sum += per;
}
else out += per;
per = y*0.07;
if(r-1 >= 0){
board[r-1][c] += per;
sum += per;
}
else out += per;
if(r+1 < N){
board[r+1][c] += per;
sum += per;
}
else out += per;
per = y*0.01;
if(r-1 >= 0 && c+1 < N){
board[r-1][c+1] += per;
sum += per;
}
else out += per;
if(r+1 < N && c+1 < N){
board[r+1][c+1] += per;
sum += per;
}
else out += per;
per = y*0.1;
if(r-1 >= 0 && c-1 >= 0){
board[r-1][c-1] += per;
sum += per;
}
else out += per;
if(r+1 < N && c-1 >= 0){
per = y*0.1;
board[r+1][c-1] += per;
sum += per;
}
else out += per;
per = y*0.05;
if(c-2 >= 0){
board[r][c-2] += per;
sum += per;
}
else out += per;
if(c-1 >= 0) board[r][c-1] += (board[r][c] - (sum + out));
else out += (board[r][c] - (sum + out));
board[r][c] = 0;
total_out += out;
break;
//아래쪽
case 1:
per = y*0.02;
if(c-2 >= 0){
board[r][c-2] += per;
sum += per;
}
else out += per;
if(c+2 < N) {
board[r][c+2] += per;
sum += per;
}
else out += per;
per = y*0.07;
if(c-1 >= 0){
board[r][c-1] += per;
sum += per;
}
else out += per;
if(c+1 < N){
board[r][c+1] += per;
sum += per;
}
else out += per;
per = y*0.01;
if(r-1 >= 0 && c+1 < N){
board[r-1][c+1] += per;
sum += per;
}
else out += per;
if(r-1 >= 0 && c-1 >= 0){
board[r-1][c-1] += per;
sum += per;
}
else out += per;
per = y*0.1;
if(r+1 < N && c-1 >= 0){
board[r+1][c-1] += per;
sum += per;
}
else out += per;
if(r+1 < N && c+1 < N){
board[r+1][c+1] += per;
sum += per;
}
else out += per;
per = y*0.05;
if(r+2 < N){
board[r+2][c] += per;
sum += per;
}
else out += per;
if(r+1 < N) board[r+1][c] += (board[r][c] - (sum + out));
else out += (board[r][c] - (sum + out));
board[r][c] = 0;
total_out += out;
break;
//오른쪽
case 2:
per = y*0.02;
if(r-2 >= 0){
board[r-2][c] += per;
sum += per;
}
else out += per;
if(r+2 < N) {
board[r+2][c] += per;
sum += per;
}
else out += per;
per = y*0.07;
if(r-1 >= 0){
board[r-1][c] += per;
sum += per;
}
else out += per;
if(r+1 < N){
board[r+1][c] += per;
sum += per;
}
else out += per;
per = y*0.01;
if(r-1 >= 0 && c-1 >= 0){
board[r-1][c-1] += per;
sum += per;
}
else out += per;
if(r+1 < N && c-1 >= 0){
board[r+1][c-1] += per;
sum += per;
}
else out += per;
per = y*0.1;
if(r-1 >= 0 && c+1 < N){
board[r-1][c+1] += per;
sum += per;
}
else out += per;
if(r+1 < N && c+1 < N){
board[r+1][c+1] += per;
sum += per;
}
else out += per;
per = y*0.05;
if(c+2 < N){
board[r][c+2] += per;
sum += per;
}
else out += per;
if(c+1 < N) board[r][c+1] += (board[r][c] - (sum + out));
else out += (board[r][c] - (sum + out));
board[r][c] = 0;
total_out += out;
break;
//위쪽
case 3:
per = y*0.02;
if(c-2 >= 0){
board[r][c-2] += per;
sum += per;
}
else out += per;
if(c+2 < N) {
board[r][c+2] += per;
sum += per;
}
else out += per;
per = y*0.07;
if(c-1 >= 0){
board[r][c-1] += per;
sum += per;
}
else out += per;
if(c+1 < N){
board[r][c+1] += per;
sum += per;
}
else out += per;
per = y*0.01;
if(r+1 < N && c+1 < N){
board[r+1][c+1] += per;
sum += per;
}
else out += per;
if(r+1 < N && c-1 >= 0){
board[r+1][c-1] += per;
sum += per;
}
else out += per;
per = y*0.1;
if(r-1 >= 0 && c-1 >= 0){
board[r-1][c-1] += per;
sum += per;
}
else out += per;
if(r-1 >= 0 && c+1 < N){
board[r-1][c+1] += per;
sum += per;
}
else out += per;
per = y*0.05;
if(r-2 >= 0){
board[r-2][c] += per;
sum += per;
}
else out += per;
if(r-1 >= 0) board[r-1][c] += (board[r][c] - (sum + out));
else out += (board[r][c] - (sum + out));
board[r][c] = 0;
total_out += out;
break;
}
}
void move_tornado(){
//맨 처음 토네이도의 위치 = 가운데, 토네이도의 방향 = 좌
int tc = N/2;
int tr = N/2;
int dir = 0;
//토네이도 이동 -> 규칙 적용 => O(N^2)
for(int i=1; i<=N; i++){
for(int j=0; j<2; j++){
for(int k=1; k<=i; k++){
//모래가 흩뿌려지는 y 위치
int yr = tr+dr[dir];
int yc = tc+dc[dir];
//토네이도 이동
tr = yr;
tc = yc;
//토네이도가 (0, 0)에 도달한 경우, 모래 흩뿌리고 종료한다
if(i==N && k==N-1){
spread_sand(yr, yc, dir);
cout << total_out <<endl;
return;
}
//y값이 0이라면 흩뿌려도 변함 없으므로, 무시한다
if(board[yr][yc] == 0) continue;
//y 위치의 모래 흩뿌리기
spread_sand(yr, yc, dir);
}
//방향 전환하기
dir = (dir+1) % 4;
}
}
}
int main(int argc, const char * argv[]) {
cin >> N;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
cin >> board[i][j];
}
}
move_tornado();
return 0;
}
//시간복잡도 = O(N^2), 공간복잡도 = O(N^2)728x90
반응형
'코테 노트 > 백준' 카테고리의 다른 글
| 백준 17822 원판 돌리기 C++ (0) | 2021.10.03 |
|---|---|
| 백준 3686 성냥개비 Python 3 (0) | 2021.10.02 |
| 백준 20058 마법사 상어와 파이어스톰 C++ (0) | 2021.09.15 |
| 백준 19238 스타트 택시 C++ (0) | 2021.09.15 |
| 백준 14716 현수막 C++ (0) | 2021.08.31 |