글 읽기 - 마법사 상어와 복제 시간초과

xlfxmvhs159 2년 전 1

자꾸 시간초과가 나는데 이유를 잘 모르겠네요ㅜㅠ

혹시 고쳐야할부분이 있을까요? moveFish 부분에서 많이 걸리는거같은데 다른 솔루션이랑 비교해도 비슷해서 잘 못찾겠네요 ㅠ

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

public class Main {
	static int M;
	static int S;
	static int sharkR;
	static int sharkC;
	static int maxKilled;
	static int[] route;
	static LinkedList<Integer>[][] fishArray;
	static int[][] smellArray;
	static int[] dirY = { 0, -1, -1, -1, 0, 1, 1, 1 };
	static int[] dirX = { -1, -1, 0, 1, 1, 1, 0, -1 };

	static int[] sharkDir = { 1, 2, 3, 4 };
	static int[] sharkY = { 0, -1, 0, 1, 0 };
	static int[] sharkX = { 0, 0, -1, 0, 1 };

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);

		M = sc.nextInt();
		S = sc.nextInt();
		fishArray = new LinkedList[4][4];
		
		for (int i = 0; i < 4; i++) {
			for (int q = 0; q < 4; q++) {
				fishArray[i][q] = new LinkedList<>();
			}
		}

		for (int i = 0; i < M; i++) {
			int y = sc.nextInt() - 1;
			int x = sc.nextInt() - 1;
			int d = sc.nextInt() - 1;
			//Fish fish = new Fish(y, x, d);

			// fishes.offer(fish);
			fishArray[y][x].add(d);
		}
		sharkR = sc.nextInt() - 1;
		sharkC = sc.nextInt() - 1;
		smellArray = new int[4][4];
		
		int count = 0;
		while (count < S) {
			// copy
			LinkedList<Integer>[][] cpy = new LinkedList[4][4];
			
			//System.out.println(0);
			for (int i = 0; i < 4; i++) {
				for (int q = 0; q < 4; q++) {
					cpy[i][q] = new LinkedList<>();
				}
			}
			for (int i = 0; i < 4; i++) {
				for (int q = 0; q < 4; q++) {
					//for (int z = 0; z < fishArray[i][q].size(); z++) {
						cpy[i][q] = fishArray[i][q];
					
				}
			}

			maxKilled = 0;
			route = new int[3];
			// System.out.println(1);
			moveFish();
			// System.out.println(2);
			eraseSmell();
			// System.out.println(3);
			bestRoute(0, new int[3]);
			// System.out.println(4);
			leaveSmell();
			// System.out.println(5);
			
			for (int i = 0; i < 4; i++) {
				for (int q = 0; q < 4; q++) {
					for (int d: cpy[i][q]) {
						fishArray[i][q].add(d);
					}
				}
			}
			//System.out.println(6);
			
			// System.out.println(sharkR + " " + sharkC);
			// System.out.println(smells);
			count++;
		}
		
		int sum = 0;
		for (int i = 0; i < 4; i++) {
			for (int q = 0; q < 4; q++) {
				sum += fishArray[i][q].size();
			}
		}
		
		System.out.print(sum);

	}

	static void eraseSmell() {

		for (int i = 0; i < 4; i++) {
			for (int q = 0; q < 4; q++) {
				smellArray[i][q] = Math.max(0, smellArray[i][q] - 1);
			}
		}
	}

	static void leaveSmell() {
		
		//Shark bestRoute = sharks.pollFirst();
		// System.out.print(bestRoute);
		//int[] dirc = bestRoute.dirc;

		for (int i = 0; i < route.length; i++) {
			sharkR = sharkR + sharkY[route[i]];
			sharkC = sharkC + sharkX[route[i]];

			if (fishArray[sharkR][sharkC].size() != 0) {
				smellArray[sharkR][sharkC] = 2;
				fishArray[sharkR][sharkC].clear();
			}
		}
	}

	static int moveShark(int[] dirc) {
		int tSharkR = sharkR;
		int tSharkC = sharkC;
		int killed = 0;

		boolean isPossible = true;
		boolean[][] vs = new boolean[4][4];

		for (int e : dirc) {
			tSharkR = tSharkR + sharkY[e];
			tSharkC = tSharkC + sharkX[e];

			if (tSharkR < 0 || tSharkR >= 4 || tSharkC < 0 || tSharkC >= 4) {
				isPossible = false;
				break;
			}

			if (!vs[tSharkR][tSharkC]) {
				killed += fishArray[tSharkR][tSharkC].size();
				vs[tSharkR][tSharkC] = true;
			}
		}

		// 이동 가능할때
		if (isPossible) {
			return killed;
		}
		else {
			return -1;
		}
	}

	static void bestRoute(int cnt, int[] temp) {
		if (cnt == 3) {
			int killed = moveShark(temp);
			if (killed > maxKilled) {
				maxKilled = killed;
				
				for (int i = 0; i < 3; i++) {
					route[i] = temp[i];
				}
			}
			return;
		}

		for (int i = 0; i < 4; i++) {
			temp[cnt] = sharkDir[i];
			bestRoute(cnt + 1, temp);
			temp[cnt] = 0;
		}
	}

	static boolean isPossible(int ny, int nx) {
		if (ny < 0 || nx < 0 || ny >= 4 || nx >= 4) {
			return false;
		}

		if (ny == sharkR && nx == sharkC) {
			return false;
		}

		if (smellArray[ny][nx] != 0) {
			return false;
		}

		return true;
	}

	static void moveFish() {
		LinkedList<Integer>[][] cpy = new LinkedList[4][4];

		for (int i = 0; i < 4; i++) {
			for (int q = 0; q < 4; q++) {
				cpy[i][q] = new LinkedList<>();
			}
		}
		
		for (int y = 0; y < 4; y++) {
			for (int q = 0; q < 4; q++) {
				
				for (int z = 0; z < fishArray[y][q].size(); z++) {
					boolean isPossible = false;
					int fish = fishArray[y][q].get(z);
					// 45도 이동
					int curDir = fish + 1;

					for (int i = 0; i < 8; i++) {
						curDir = (curDir + 8 - 1) % 8;

						int ny = y + dirY[curDir];
						int nx = q + dirX[curDir];

						if (!isPossible(ny, nx)) {
							continue;
						}
						// 이동 가능하면 이동
						else {
							isPossible = true;
							cpy[ny][nx].add(curDir);
							break;
						}
					}
					
					if (!isPossible) {
						cpy[y][q].add(fish);
					}
				}
			}
		}
		
		fishArray = cpy;
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

마법사 상어와 복제 시간초과

xlfxmvhs159 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말