[BOJ] 17143 낚시왕 - Java

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

17143번: 낚시왕

[풀이]

1. 낚시왕을 이동시키고, 해당 열에 제일 가까운 상어를 없앤다.
2. 상어들을 이동시킨다. (한번에 이동시켜야 하므로 Map에 바로 상어들을 이동시키지 않고, Copy를 이용하여 거기에 값들을 넣어놓는다.)
3. Copy에 있는 상어들을 Map에 넣는다. 그 후 한 칸에 2마리 이상 있으면 제일 사이즈 큰 애만 남기고 삭제

- 사이즈 제일 큰 상어를 골라내기 위해서 PriorityQueue를 사용했다. PriorityQueue[][] 는 각 이중배열 칸에 우선순위 큐가 들어가는 것이다.

- Map, Copy 둘 다 PriorityQueue[][] 자료형을 사용하며, Copy는 낚시왕이 이동할 때마다 초기화해준다.

- 상어 이동은 dfs를 이용했다. 좌표범위를 벗어나면 count를 증가시키지 않고 방향만 바꿔서 다시 dfs를 호출하고, 벗어나지 않으면 count를 증가시키고 dfs를 호출해 진행방향으로 계속 진행한다. 

 

**실수한 부분

PriorityQueue의 사이즈를 잡고 for문을 돌렸는데, poll이라는 삭제 연산이 일어나므로 PriorityQueue의 사이즈도 계속 변한다는 것을 간과했다. 아래처럼 바꿔줘야 한다.

for(int s=0;s<Map[i][j].size()-1;s++) {
    Map[i][j].poll(); //제일큰거만 남기기
}
//==========수정후
int size = Map[i][j].size();
for(int s=0;s<size-1;s++) {
    Map[i][j].poll(); //제일큰거만 남기기
}

(근데 이거말고 그냥 시간을 더 줄이기 위해 다른 방법을 사용하긴 했다. 코드에서 확인할 수 있다. - 제일 큰애로 정렬해서 걔 뽑아서 새로운 우선순위큐 정의하고 거기에 넣기)

 

** 다른 사람 풀이 보고 안 부분

시간초과가 나서 도대체 뭐가 문제인가 하고 다른 부분을 계속 건드리고 있었다. 그래도 모르겠어서 결국 다른 풀이를 보았다.

간과한 부분은 바로 상어의 속력은 1000까지라는 것. 그러면 1000번까지 움직일 수 있는건데 Map의 크기는 가로세로100까지이다. 그럼 분명 겹치는 부분이 있을 것이다. -> 불필요한 반복 연산이 들어간다.

 

불필요한 반복 연산을 없애기 위해 아래 코드를 추가했다. 

if(s!=0) {
    if(d==1 || d==2) { //상하
        s = s % (R+(R-2));
    }
    else { //좌우
        s = s % (C+(C-2));
    }
}

가로 or 세로 길이를 L이라고 했을 때 L+(L-2)번 움직이면 속력0인 상태와 동일하다. 따라서 L+(L-2)번으로 속력을 나누면 반복적인 연산을 줄일 수 있다. 상하로 움직이면 L이 R이 되고, 좌우로 움직이면 L은 C이다.

 

[코드]

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

public class Main {
	static StringTokenizer st;
	static int R,C,M;
	static PriorityQueue<Shark>[][] Map;
	static PriorityQueue<Shark> [][] Copy;
	static int[] dRow = {0,-1,1,0,0};//0,상하우좌
	static int[] dCol = {0,0,0,1,-1};
	static int answer = 0;
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		//System.setIn(new FileInputStream("src/main/java/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		Map = new PriorityQueue[R+1][C+1];
		for(int i=1;i<R+1;i++) {
			for(int j=1;j<C+1;j++) {
				Map[i][j] = new PriorityQueue<>();
			}
		}
		
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			int z = Integer.parseInt(st.nextToken());
			if(s!=0) {
				if(d==1 || d==2) { //상하
					s = s % (R+(R-2));
				}
				else { //좌우
					s = s % (C+(C-2));
					//System.out.println(C+(C-1)+" "+s);
				}
			}
			
			Map[r][c].add(new Shark(s,d,z));
			System.out.println(Map[r][c]);
		}
		
		//start
		for(int c=1;c<=C;c++) { //낚시꾼 이동
			Copy = new PriorityQueue[R+1][C+1];
			for(int i=1;i<R+1;i++) {
				for(int j=1;j<C+1;j++) {
					Copy[i][j] = new PriorityQueue<>();
				}
			}
			
//			System.out.println("낚시꾼 이동 전");
//			printMap();
			
			//가장 가까운 상어 제거
			for(int r=1;r<=R;r++) {
				if(Map[r][c].size()!=0) {
					Shark getShark = Map[r][c].poll(); //상어 제거
					//System.out.println(r+","+c+" ->"+getShark);
					answer += getShark.size;
					break;
				}
			}
			
			//상어 이동
			for(int i=1;i<R+1;i++) {
				for(int j=1;j<C+1;j++) {
					//상어가 있으면 dfs
					if(Map[i][j].size()!=0) {
						Shark shark = Map[i][j].poll();
						dfs(i,j,shark,0);
					}
				}
			}
		
			//copy -> Map 넣기
			for(int i=1;i<R+1;i++) {
				for(int j=1;j<C+1;j++) {
					if(Copy[i][j].size()>0) {
						Map[i][j] = new PriorityQueue<>(Copy[i][j]);
					}
				}
			}
//			System.out.println("상어 이동 후");
//			printMap();
			
			//상어 잡아먹기
			for(int i=1;i<R+1;i++) {
				for(int j=1;j<C+1;j++) {
					//상어가 두 마리 이상이면
					if(Map[i][j].size()>=2) {
						Shark big = Map[i][j].poll();
						Map[i][j] = new PriorityQueue<>();
						Map[i][j].add(big); //제일 사이즈 큰것만 넣기
					}
				}
			}
		}
		
		System.out.println(answer);
	}
	
	static void dfs(int row, int col, Shark shark, int count) {
		//System.out.println("###"+shark +"("+ row +"," + col +") COUNT : "+count);
		if(count>=shark.speed) {
			Copy[row][col].add(shark);
			return;
		}
		int newRow = row + dRow[shark.dir];
		int newCol = col + dCol[shark.dir];
		if(0<newRow && newRow<=R && 0<newCol && newCol<=C) { //범위내면 그대로 이동
			dfs(newRow,newCol,shark,count+1);
		}
		else {
			Shark newShark = new Shark(shark.speed,changeDir(shark.dir),shark.size); //방향바꾸기
			dfs(row,col,newShark,count);
		}
	}
	
	static int changeDir(int dir) {
		switch(dir) {
		case 1:
			return 2;
		case 2:
			return 1;
		case 3:
			return 4;
		case 4:
			return 3;	
		}
		return -1;
	}
	
	static void printMap() {
		System.out.println("=================");
		for(int i=1;i<R+1;i++) {
			for(int j=1;j<C+1;j++) {
				System.out.println(i+","+j+" -> "+Map[i][j]);
			}
		}
		System.out.println("=================");
	}
	
	static class Shark implements Comparable<Shark>{
		int speed;
		int dir;
		int size;
		
		@Override
		public String toString() {
			return "Shark [speed=" + speed + ", size=" + size + ", dir=" + dir + "]";
		}

		public Shark(int speed, int dir, int size) {
			super();
			this.speed = speed;
			this.dir = dir;
			this.size = size;
		}

		@Override
		public int compareTo(Shark o) {
			// TODO Auto-generated method stub
			return Integer.compare(o.size,size);
		}
	}

}

[느낀점]

소요시간 : 2h 30min

테스트케이스만으로는 정답이었는데, 제출하니 틀렸습니다. 가 뜨고 , 시간초과가 떴다.

ㅠㅠ 테케아닌 부분에서 어떤게 틀렸는지 디버깅하는건 아직 잘 못하겠다.

한번에 갱신시켜줘야하는 것이 있다면 같은 데이터를 추가하거나 삭제하려 하지 말고, Copy를 두어서 활용하자.

반복 연산은 줄이자. (입력 조건도 잘 확인하자)