- 소요시간 : 1시간 50분
- 문제 사이트 : 백준
- 문제 수준 : 골드 3
- 문제 유형 : 구현, 시뮬레이션
- 다른 사람의 풀이를 참고 했는가 ? : X
- 문제 링크 : https://www.acmicpc.net/problem/20057
- 푼 날짜 : 2023.05.05
1. 사용한 자료구조 & 알고리즘
구현, 시뮬레이션
2. 사고과정
1. 토네이도가 움직이는 것을 어떻게 구현할 것인가?
처음에는 0,0에서부터 탐색해서 N-1까지 토네이도를 이동시키려고 했으나 토네이도가 이동하면서 단순히 값이 1개가 바뀌는 것이 아닌, 10갈래로 퍼져 나가므로 꼭 가운데부터 처리해 주어야 할거라고 생각.
그래서 queue를 이용해서 맵의 가운데에서부터 처리.
규칙을 찾고자 했는데
- 토네이도가 왼쪽, 아래, 오른쪽, 위를 반복하면서
(1칸,1칸, 2칸,2칸,3칸,3칸 ...)의 형식으로 이동하고 있었음. 그래서 queue에서 poll할 때마다 count를 증가시키고, count가 짝수면 진행하는 칸수를 늘렸음.
2. 먼지가 퍼지는 것을 어떻게 구현할 것인가?
이게 가장 까다로웠다. 빡구현 했는데, 먼지가 10개의 위치로 퍼지는데, 현재 위치에서 몇칸 떨어져있는지를 4방향 각각 다 구해서 y좌표, x좌표를 구하니 총 40가지가 나왔다. 그리고 각각의 위치마다 가중치 값 (%) 이 있으니, 그 좌표에 맞는 가중치 값도 처음에 부여해 줌으로써 처리했다.
3. 먼지가 맵 밖으로 나간 것을 어떻게 처리할 것인가?
처음에는 먼지가 맵 밖으로 벗어날 때마다 count를 증가시켜줄까 했지만, 그러지 않고 처음 map에서의 먼지의 개수를 모두 세어준 후, 토네이도는 1번만 이동하므로 토네이도가 이동하고 난 후, map에 남아있는 먼지를 세어주고 , 그 차를 구하면 맵 밖으로 벗어난 먼지의 양이다.
3. 풀이과정
- 각각의 방향마다의 먼지가 흩어지는 위치, 가중치 값을 계산함. 그리고 토네이도가 이동하는 4방향도 지정해줌.
- queue에 맵의 중간 좌표를 저장. 왼쪽, 아래, 오른쪽, 위로 이동.
- 토네이도가 1칸 이동할 때마다 먼지를 퍼뜨림.
- (종료의 조건) 토네이도가 (0,0)에 오게 된다면 현재 남아있는 맵의 먼지를 세어주고, 처음의 값과 비교해서 그 차를 구한 후 출력.
4. 소스코드
import java.util.*;
import java.io.*;
public class Main{
static int map[][];
//현재 바라보는 방향에 따라서 먼지가 흩어지는 좌표 계산
static int directionY[][]= {
{-1,1,-1,1,-1,1,-2,2,0,0},
{-1,-1,0,0,1,1,0,0,2,1},
{-1,1,-1,1,-1,1,-2,2,0,0},
{1,1,0,0,-1,-1,0,0,-2,-1}
};
static int directionX[][]= {
{1,1,0,0,-1,-1,0,0,-2,-1},
{-1,1,-1,1,-1,1,-2,2,0,0},
{-1,-1,0,0,1,1,0,0,2,1},
{-1,1,-1,1,-1,1,-2,2,0,0}
};
//먼지가 흩어지는 비율. 0.01은 1%.
static double percent[] = {0.01,0.01,0.07,0.07, 0.1 , 0.1 ,0.02 , 0.02 , 0.05 , 0 };
static int sum = 0;
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
map=new int[n][n];
for(int i=0;i<n;i++) {
st=new StringTokenizer(br.readLine());
for(int j=0;j<n;j++) {
map[i][j] = Integer.parseInt(st.nextToken());
sum+=map[i][j];
}
}
//토네이도가 지나감
tornado();
}
//맵을 세어주는 함수. (0,0) 좌표에 도달했을 때 세어줌.
//처음에 맵에 있던 먼지에서 현재 먼지값을 뺀 값을 출력
public static void countMap() {
int next = 0;
for(int i=0;i<map.length;i++) {
for(int j=0;j<map.length;j++) {
next+=map[i][j];
}
}
System.out.println(sum-next);
System.exit(0);
}
public static void tornado() {
Queue<Integer[]> queue=new LinkedList<>();
//가운데 좌표 (y,x), 진행방향, 반복횟수를 넣음
queue.add(new Integer[] {map.length/2,map.length/2,0,1});
int count = 0;
//4방향의 진행방향
int dy[] = {0,1,0,-1};
int dx[] = {-1,0,1,0};
while(true) {
Integer temp[]=queue.poll();
int nowY=temp[0];
int nowX=temp[1];
int dir = temp[2];
int cycle = temp[3];
count++;
for(int i=0;i<cycle;i++) {
//진행 방향으로 1칸 이동
int nextY= nowY + dy[dir];
int nextX= nowX + dx[dir];
//먼지가 퍼짐.
spreadDirt(nextY,nextX,dir);
//(0,0)에 도달시 맵에서 벗어난 먼지의 개수를 세어줌
if(nextY==0&&nextX==0)
countMap();
nowY=nextY;
nowX=nextX;
}
//진행방향이 2번 바뀔 때마다 탐색 길이가 1씩 늘어남.
if(count%2==0)
cycle++;
//큐가 수행된후 진행방향을 바꿈.
dir++;
if(dir==4) dir=0;
queue.add(new Integer[] {nowY,nowX,dir,cycle});
}
}
//먼지를 퍼뜨리는 함수
public static void spreadDirt(int y,int x,int dir) {
//현재 좌표의 먼지를 저장.
int save = map[y][x];
//먼지가 퍼지는 10방향
for(int i=0;i<directionX[0].length;i++) {
int nextY=y+directionY[dir][i];
int nextX=x+directionX[dir][i];
double per = percent[i];
int dirt = (int) (per * save );
//현재 좌표의 먼지를 줄임.
map[y][x] -= dirt;
//다음 좌표가 맵을 벗어나면 그냥 먼지가 맵 밖으로 없어진 것.
if(nextY<0||nextX<0||nextY>=map.length||nextX>=map.length)
continue;
//맵을 벗어나지 않았다면, i가 9인 것은 문제 그림에서의 a의 위치임.
// 먼지가 흩어지고 현재 좌표에 남아있는 먼지만큼 다음 좌표에 더함
// -> i가 9가 아닌 0~8이라면 문제의 9가지 비율이 적힌 칸임. 계산된 값을 더해줌
if(i==9) {
map[nextY][nextX] += map[y][x];
}else {
map[nextY][nextX] += dirt;
}
}
//원래 좌표의 먼지는 0이 됨.
map[y][x] = 0;
}
}
5. 결과
6. 회고
구현 문제 너무 재밌고
풀고 난 후 다른 사람들은 어떻게 풀었나 봤는데
토네이도 지나간 거랑 먼지 퍼지는 걸 거의 나랑 똑같이 푼 사람들이 많았다.
사람의 생각이 다 비슷한가보다.
하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212
아이스 카라멜 마끼아또보단 뜨거운 아메리카노를, 맨투맨보단 니트를, 웹툰보단 책을 좋아하고 싶은 사람