문제
BOJ 20056: 마법사 상어와 파이어볼 https://www.acmicpc.net/problem/20056
풀이
조건
-
파이어볼의
위치는 (r, c),질량은 m이고,방향은 d,속력은 s이다. 위치 (r, c)는 r행 c열을 의미한다.- 아래 코드에서 r은 x, c는 y로 해서 풀었다.
-
격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.
- 쉽게 말해,
범위를 넘어가면 그 반대쪽 위치로 이동한다는 뜻이다.
- 쉽게 말해,
-
파이어볼의 방향은 어떤 칸과 인접한 8개의 칸의 방향을 의미하며, 정수로는 다음과 같다.
-
마법사 상어가 모든 파이어볼에게 이동을 명령하면 다음이 일들이 일어난다.
- 모든 파이어볼이 자신의 방향 d로 속력 s칸 만큼 이동한다.
- 이동하는 중에는 같은 칸에 여러 개의 파이어볼이 있을 수도 있다.
- 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다.
- 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다.
- 파이어볼은
4개의 파이어볼로 나누어진다. - 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다.
- 질량은
(합쳐진 파이어볼 질량의 합)/5이다. - 속력은
(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)이다. - 합쳐지는 파이어볼의
방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고,그렇지 않으면 1, 3, 5, 7이 된다.
- 질량은
- 질량이 0인 파이어볼은 소멸되어 없어진다.
- 모든 파이어볼이 자신의 방향 d로 속력 s칸 만큼 이동한다.
풀이 순서
파이어볼의 현재 위치 등 정보를 담을Queue 배열(que)을 생성 및 초기화한다.- Queue 배열(que)에 입력 받은 파이어볼 객체를 삽입한다.
- 입력받은 명령 횟수 만큼 반복한다.
- 파이어볼을 모두 이동시킨다.
파이어볼의 새로운 위치를 기록해놓을Queue 배열(extQue)을 생성 및 초기화한다.- 각 좌표를 탐색하며 수행
- 파이어볼의 방향과 속력만큼 이동시킨다.
extQue에이동이 완료된 좌표와 객체를 넣는다.
- 원본 Queue배열인
que에extQue 값을 복사한다.
- 각 위치에 파이어볼이 2개 이상 있으면 해당 위치의 파이어볼들을 합치고 4개로 나눈다.
- 해당 위치에 있는 파이어볼들의 질량과 속력을 더한 각각의 값으로 새로운 질량과 속력을 구한다.
- 방향의 홀, 짝 갯수를 구분하여 새로운 방향을 얻은 파이어볼 4개를 원본 Queue배열인 que에 넣는다.
- 파이어볼을 모두 이동시킨다.
- 현재 남아 있는 파이어볼들의 질량 총합을 구해 출력한다.
코드
import java.util.*;
import java.io.*;
public class Main {
static int N, M, K;
static int[][] info;
static Queue<Fire>[][] que;
static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1}; // 방향
static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken()); // 맵 크기
M = Integer.parseInt(st.nextToken()); // 파이어볼 정보 갯수
K = Integer.parseInt(st.nextToken()); // 이동 명령 횟수
info = new int[M][5]; // 행, 열, 질량, 속력, 방향
// Queue 배열 생성 및 초기화
que = new LinkedList[N+1][N+1];
for(int i=0; i<=N; i++) {
for(int j=0; j<=N; j++) {
que[i][j] = new LinkedList<Fire>();
}
}
// Queue 배열에 입력 받은 파이어볼 객체 삽입
for(int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine(), " ");
for(int j=0; j<5; j++) {
info[i][j] = Integer.parseInt(st.nextToken());
}
Fire f = new Fire(info[i][0], info[i][1], info[i][2], info[i][3], info[i][4]);
que[f.x][f.y].add(f);
}
// 명령 횟수 만큼 반복
for(int k=1; k<=K; k++) {
// 각 파이어볼이 이동함
move();
// 위치에 있는 파이어볼들을 합치고 4개로 나눔
combine();
}
// 답 출력
int ans = 0;
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) {
if(!que[i][j].isEmpty()) {
while(!que[i][j].isEmpty()) {
Fire f = que[i][j].poll();
ans += f.m;
}
}
}
}
System.out.println(ans);
}
// 위치에 있는 파이어볼들을 합치고 4개로 나눌 메소드
static void combine() {
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) {
// 해당 위치에 파이어볼이 2개 이상 있다면
if(que[i][j].size() >= 2) {
int mSum = 0; // 질량의 합
int sSum = 0; // 속력의 합
int queSize = que[i][j].size(); // 파이어볼의 갯수
ArrayList<Boolean> even = new ArrayList<>(); // 짝수 방향을 넣을 리스트
ArrayList<Boolean> odd = new ArrayList<>(); // 홀수 방향을 넣을 리스트
while(!que[i][j].isEmpty()) {
Fire f = que[i][j].poll();
mSum += f.m; // 질량을 더함
sSum += f.s; // 속력을 더함
// 방향의 홀, 짝 을 구분해서 리스트에 넣어줌
if(f.d % 2 == 1) {
odd.add(true);
} else {
even.add(true);
}
}
int nM = mSum / 5; // 새로운 질량
int nS = sSum / queSize; // 새로운 속력
// 새로운 질량이 0이면 넘어감
if(nM == 0) {
continue;
}
// 방향이 모두 짝수이거나 홀수라면
if(even.size() == 0 || odd.size() == 0) {
// 방향: 0, 2, 4, 6
que[i][j].add(new Fire(i, j, nM, nS, 0));
que[i][j].add(new Fire(i, j, nM, nS, 2));
que[i][j].add(new Fire(i, j, nM, nS, 4));
que[i][j].add(new Fire(i, j, nM, nS, 6));
} else {
// 방향: 1, 3, 5, 7
que[i][j].add(new Fire(i, j, nM, nS, 1));
que[i][j].add(new Fire(i, j, nM, nS, 3));
que[i][j].add(new Fire(i, j, nM, nS, 5));
que[i][j].add(new Fire(i, j, nM, nS, 7));
}
}
}
}
}
// 파이어볼 이동시키는 메소드
static void move() {
// 파이어볼의 새로운 위치를 기록해놓을 Queue 배열 : extQue
Queue<Fire>[][] extQue = new LinkedList[N+1][N+1];
for(int i=0; i<=N; i++) {
for(int j=0; j<=N; j++) {
extQue[i][j] = new LinkedList<Fire>();
}
}
// 각 좌표를 탐색하며 수행
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) {
// 해당 que에 파이어볼이 들어 있다면
if(!que[i][j].isEmpty()) {
while(!que[i][j].isEmpty()) {
Fire f = que[i][j].poll();
int curX = f.x;
int curY = f.y;
// 속력 만큼 이동
for(int s=1; s<=f.s; s++) {
curX += dx[f.d];
curY += dy[f.d];
// 새로운 위치가 범위를 넘어가면 반대편 쪽으로 넘어가게 함
// 문제 조건 잘 볼 것
if(curX <= 0) {
curX = N;
} else if(curX > N) {
curX = 1;
}
if(curY <= 0) {
curY = N;
} else if(curY > N) {
curY = 1;
}
}
Fire nf = new Fire(curX, curY, f.m, f.s, f.d);
// extQue에 새로운 위치로 이동한 파이어볼을 넣음
extQue[curX][curY].add(nf);
}
}
}
}
// 원본 Queue배열인 que에 extQue 값을 복사함
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) {
if(!extQue[i][j].isEmpty()) {
while(!extQue[i][j].isEmpty()) {
Fire f = extQue[i][j].poll();
que[i][j].add(f);
}
}
}
}
}
// 파이어볼 정보를 담을 객체
static class Fire{
int x, y, m, s, d;
Fire(int x, int y, int m, int s, int d){
this.x = x;
this.y = y;
this.m = m;
this.s = s;
this.d = d;
}
}
}정리
격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.라는 조건 해석을 못해서 시간 낭비를 했다.- 파이어볼을 이동시킬 때 복사본(extQue)을 사용하지 않아서 시간 낭비를 했다.
