[백준] 20056.마법사 상어와 파이어볼 / 시뮬레이션

@시뮬레이션 / 1h

2020 하반기 삼성전자 코딩테스트 오전(DS) 2번 문제.

그때 문제 잘못 읽어서 삽질한것만 생각하면...ㅜㅜ

 

근데 그때랑 문제의 전체 흐름은 똑같은데, 조건이 살짝 다른 것 같다.

그때는 일단 이동한 후, 다음 해에 부딪힌 행성이 터졌던 것 같은데.. 뭐 여튼

 

 

문제 링크

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

20056번: 마법사 상어와 파이어볼

 

구현 포인트

시뮬레이션이니까, 문제에서 시키는 대로 차근차근 하면 된다.

큰 로직은 이렇게 구현했다.

 

for (K년, 총 이동해야 하는 횟수) {

     ballMove(); //임시 맵에다가 파이어볼 움직이기

     drawMap(); //임시 맵에 옮겨놓은 파이어볼들을 원래 맵에 그려주기, 터진 볼이 있다면 그것도 여기서 처리

}

 

삽질 포인트

3번 테스트케이스에서 값이 자꾸 다르게 나와서, 왜이러나 했더니

합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다.

이 부분을 구현할 때 방향%2 한 값이 같은지를 비교했어야 하는데, 방향 값 자체를 비교해서..

그래서 잘못 퍼져나가서 답이 이상하게 나왔었다.

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
	
	static class Node {
		int m, s, d;
		Node (int m, int s, int d) {
			this.m = m;
			this.s = s;
			this.d = d;
		}
	}
	static int N, M, K;
	static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
	static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
	static LinkedList<Node>[][] map, tempMap;
	
	public static void main(String[] args) throws Exception {
		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());
		
		map = new LinkedList[N][N];
		tempMap = new LinkedList[N][N];
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = new LinkedList<Node>();
				tempMap[i][j] = new LinkedList<Node>();
			}
		}
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken()) - 1;
			int c = Integer.parseInt(st.nextToken()) - 1;
			int m = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			map[r][c].add(new Node(m, s, d));
		}
		
		for (int i = 0; i < K; i++) {
			ballMove();
			drawMap();
		}
		System.out.println(getSum());
	}

	private static int getSum() {
		int sum = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				for (int k = 0; k < map[i][j].size(); k++) {
					sum += map[i][j].get(k).m;
				}
			}
		}
		return sum;
	}

	private static void drawMap() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (tempMap[i][j].size() == 1) {
					map[i][j].add(tempMap[i][j].removeFirst());
				} else if (tempMap[i][j].size() > 1) {
					int weigthSum = tempMap[i][j].get(0).m;
					int speedSum = tempMap[i][j].get(0).s;
					int prevDir = tempMap[i][j].get(0).d % 2;
					boolean sameDir = true;
					
					for (int k = 1; k < tempMap[i][j].size(); k++) {
						weigthSum += tempMap[i][j].get(k).m;
						speedSum += tempMap[i][j].get(k).s;
						if (prevDir != tempMap[i][j].get(k).d % 2) 
							sameDir = false;
					}
					
					if (weigthSum / 5 == 0) {
						tempMap[i][j].clear();
						continue;
					}
					
					int initDir = sameDir ? 0 : 1;
					for (int k = 0; k < 4; k++) {
						map[i][j].add(new Node(weigthSum / 5, speedSum / tempMap[i][j].size(), initDir + k * 2));
					}
					tempMap[i][j].clear();
				}
			}
		}
	}

	private static void ballMove() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				for (int k = 0, size = map[i][j].size(); k < size; k++) {
					int nx = (i + map[i][j].get(0).s * dx[map[i][j].get(0).d] + 1000 * N) % N;
					int ny = (j + map[i][j].get(0).s * dy[map[i][j].get(0).d] + 1000 * N) % N;
					tempMap[nx][ny].add(map[i][j].removeFirst());
				}
			}
		}
	}
}

너무 오랜만에 풀어서.. 시간복잡도 효율성 이런거 생각 안하고 그냥 풀었다. 나중에 다시 최적화 해봐야지!

끝!