글 읽기 - 29290번 시간초과 이유가 무엇일까요? java

oiehso0 1년 전 0

시간초과가 발생합니다.. 어느 부분때문일까요?
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;

public class Main {
	
	
	
	static int[] dr8 = {0, -1, -1, -1, 0, 1, 1, 1};
	static int[] dc8 = {-1, -1, 0, 1, 1, 1, 0, -1};

	//0 1 2 3 위 왼 아래 오른 
	static int[] dr4 = {-1, 0, 1, 0};
	static int[] dc4 = {0, -1, 0, 1};
	
	static int[] numbers;
	
	static int skr;
	static int skc;
	
	
	static int[][] map;
	static int[][] smellMap;
	static boolean[][] visited;
	
	static int maxFishCnt;
	static int[] maxMoves = new int[3];
	static int maxR;
	static int maxC;
	
	static HashMap<Fish, Integer> fishList;
	static HashMap<Fish, Integer> newFishList;
	
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		fishList = new HashMap<>();
		
		st = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(st.nextToken());
		int S = Integer.parseInt(st.nextToken());

		smellMap = new int[4][4];
		
		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 d = Integer.parseInt(st.nextToken()) - 1;
			Fish tmpFish = new Fish(r, c, d);
			if(fishList.containsKey(tmpFish)) {
				fishList.put(tmpFish, fishList.get(tmpFish) + 1);
			}
			else {
				fishList.put(tmpFish, 1);
			}
			//System.out.println(r + " " + c +" "+ d);
		}
		
		st = new StringTokenizer(br.readLine());
		skr = Integer.parseInt(st.nextToken()) - 1;
		skc = Integer.parseInt(st.nextToken()) - 1;
		
		for (int i = 0; i < S; i++) {
			//System.out.println("\nstage : " + i);
			//System.out.println("skr : " + skr + " " + "skc : " + skc + "\n");
			
			//savePosition();

			moveFish();
			numbers = new int[3];
			maxFishCnt = -1;
			maxMoves = new int[3];
			printMap();
			//System.out.println("moveShark");
			moveShark(skr, skc, 0); //cnt, fishcnt
			printMap();
			makeSmell(i);
			removeSmell(i);
			addFish();
			//System.out.println("after addFish");
			printMap();

			//System.out.println("skr : " + skr + " " + "skc : " + skc);
			
		}
		
		int ans = 0;
		for (Fish key : fishList.keySet()) {
			ans += fishList.get(key);
		}
		
		System.out.println(ans);
		
		
		//combR(0, 0);
		
		//1.savePosition() 현재 물고기의 위치와 방향을 기억해둠
		//2.moveFish() 이동할 수 있으면 하고 못하면 방향도 위치도 그대로 
		//3.moveShark() 3칸이동 물고기 제거 최우선 동점일때 사전순 
		//4.removeSmell() 2회가 지난 냄새자국은 제거 
		//5.copyFish() 1번의 물고기 방향과 위치에 복사 

	}
	
	private static void addFish() {
		System.out.println("addFish");
		// TODO Auto-generated method stub
		
		for (Fish key : newFishList.keySet()) {
			if(fishList.containsKey(key)) {
				fishList.put(key, newFishList.get(key) + fishList.get(key));
			}
			else {
				fishList.put(key, newFishList.get(key));
			}
		}
		
		map = new int[4][4];
		for (Fish key : fishList.keySet()) {
				map[key.r][key.c] += fishList.get(key);	//상어가 스캔할 수 있게 맵에 담아줌
			
		}
		
	}

	private static void removeSmell(int t) {
		// TODO Auto-generated method stub
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if(smellMap[i][j] == t )
					smellMap[i][j] = 0;
			}
		}
	}

	private static void makeSmell(int i) { //범위를 넘어가거나 두번 방문하는 경우가 있겠지만 무의미.
		System.out.println("makeSmell");
		// TODO Auto-generated method stub
		int nr = skr;
		int nc = skc;
		for (int j = 0; j < 3; j++) {
			int d = maxMoves[j];
			nr += dr4[d];
			nc += dc4[d];

			//System.out.println("maxMoves[j] : " + maxMoves[j]);
			LinkedList<Fish> fishKeys = new LinkedList<>();
			Iterator<Fish> it = newFishList.keySet().iterator();
			while(it.hasNext()) {
				Fish key = it.next();
				if(key.r == nr && key.c == nc) {
					smellMap[nr][nc] = i + 2;
					fishKeys.add(key);
					//System.out.println("remove nr: " + nr + " nc: " + nc);
				}
			}
			for (int k = 0; k < fishKeys.size(); k++) {
				//System.out.println("fishKeys.get(k)" + fishKeys.get(k).r +" "+ fishKeys.get(k).c+ " "+ fishKeys.get(k).d);
				newFishList.remove(fishKeys.get(k));
			}
			
		}
		skr = maxR;
		skc = maxC;
	}

	private static void moveShark(int skr2, int skc2, int cnt) {
		System.out.println("moveShark");
		// TODO Auto-generated method stub
		if(cnt == 3) {	//이동방향 조합이 완성됨.
			visited = new boolean[4][4];
			int fishCnt = 0;
			int nr = skr2;
			int nc = skc2;
			boolean check = false;
			for (int i = 0; i < 3; i++) {
				nr += dr4[numbers[i]];
				nc += dc4[numbers[i]];
				if(nr < 0 || nc < 0 || nr >= 4 || nc >= 4) {
					return;
				}
				if(!visited[nr][nc]) {	//방문한 적 없을 때
					visited[nr][nc] = true;
					fishCnt += map[nr][nc];
					if(maxFishCnt < fishCnt) {
						check = true;
					}
					
				}
				if(check) {
					maxR = nr;
					maxC = nc;
				}
			}
			
			if(maxFishCnt < fishCnt) {
				maxFishCnt = fishCnt;
				maxMoves[0] = numbers[0];
				maxMoves[1] = numbers[1];
				maxMoves[2] = numbers[2];
				
				//System.out.println(maxFishCnt);
				//System.out.println("best dir: " + Arrays.toString(numbers) + "\n");
			}
			
			return;
		}
		for (int i = 0; i < 4; i++) {
			numbers[cnt] = i;
			moveShark(skr2, skc2, cnt + 1);
		}
	}
	


	private static void moveFish() {
		System.out.println("moveFish");
		// TODO Auto-generated method stub
		newFishList = new HashMap<>();
		map = new int[4][4];
		
		for (Fish key : fishList.keySet()) {
			boolean check = false;
			int tmpD = key.d;
			for (int d = 0; d < 8; d++) {
				int nr = key.r + dr8[tmpD];
				int nc = key.c + dc8[tmpD];
				if(nr < 0 || nc < 0 || nr >= 4 || nc >= 4 || smellMap[nr][nc] != 0 || 
						(nr == skr && nc == skc )) {	// 갈 수 없으면
					tmpD = (tmpD - 1 < 0) ? 7 : tmpD - 1;
					continue;
				}
				Fish tmpFish = new Fish(nr, nc, tmpD);
				if(newFishList.containsKey(tmpFish)) {
					newFishList.put(tmpFish, newFishList.get(tmpFish) + fishList.get(key));
				}
				else {
					newFishList.put(tmpFish, fishList.get(key));
				}
				map[nr][nc] += fishList.get(key);	//상어가 스캔할 수 있게 맵에 담아줌
				check = true;
				break;
			}
			if(check != true) {	//물고기가 갈곳이 없으면 상태 그대로 저장
				if(newFishList.containsKey(key)) {
					newFishList.put(key, newFishList.get(key) + fishList.get(key));
				}
				else {
					newFishList.put(key, fishList.get(key));
				}
				map[key.r][key.c] += fishList.get(key);
			}
		}
		
	}
	
	private static void printMap() {
		for (int i = 0; i < 4; i++) {
			//System.out.println(Arrays.toString(map[i]));
		}
	}
	
	




	
	static class Fish{
		int r = 0;
		int c = 0;
		int d = 0;
		
		Fish(int r, int c, int d){
			this.r = r;
			this.c = c;
			this.d = d;
		}
		
	}

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

문제

출처

ICPC

29290번 시간초과 이유가 무엇일까요? java

oiehso0 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
