백준 17143번: 낚시왕 [구현][시뮬레이션][Java]

www.acmicpc.net/problem/17143

17143번: 낚시왕

1. 낚시왕 이동

2. 상어 잡기 - 가장 가까운 한마리만 잡고 바로 break

3. 상어 이동

3-1. 이동 후 같은 자리에 있는 상어들의 크기비교

package algorithm.boj;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Fun17143 {

	public static int R, C, M, ans = 0;
	public static int fisherman = 0;
	public static int map[][];
	public static int afterMap[][]; //상어 이동한 후 같은자리 체킹을 위한 map
	public static int dx[] = {0,-1,1,0,0}; //북, 남, 동, 서
	public static int dy[] = {0,0,0,1,-1};
	public static Queue<Shark> Q = new LinkedList<Shark>();
	public static Queue<Shark> afterQ;// = new LinkedList<Shark>();
//	public static ArrayList<Shark> list = new ArrayList<Shark>();
	

	public static void main(String[] args) throws FileNotFoundException {

		System.setIn(new FileInputStream("sample_input.txt"));
		Scanner sc = new Scanner(System.in);	
		R = sc.nextInt();
		C = sc.nextInt();
		M = sc.nextInt();
		map = new int[R+1][C+1];
		for (int i = 0; i < M; i++) {
			int r = sc.nextInt();
			int c = sc.nextInt();
			int s = sc.nextInt();
			int d = sc.nextInt();
			int z = sc.nextInt();
			map[r][c]=z;
			Q.add(new Shark(r,c,s,d,z));
		}
		
		//run
		run();
		System.out.println(ans);
	}
	
	public static void run() {
		
		//낚시왕이 가장 오른쪽으로 이동할때까지 반복
		while(fisherman < C) {
			
			//1. 낚시왕 이동
			fisherman++;
            
			//2. 상어 잡기
			boolean isCatch = false;
			for (int i = 1; i <= R; i++) {
				if(map[i][fisherman]>0) {
					while(true) {
						Shark s = Q.poll();
						//가장 바닥과 가까운 상어를 만났는가? (상어 잡기)
						if(i==s.row && fisherman==s.col) {
//							System.out.println("잡았다!");
							isCatch=true;
							ans+=map[i][fisherman];
							break;
						}
						//상어 잡은거아니면 꺼낸거 다시 Q에 넣자
						Q.add(s);
					}
				}
				//하나만 찾으면 되니 바로 break
				if(isCatch)
					break;
			}
			
			//3. 상어 이동
			afterMap = new int[R+1][C+1];
			afterQ = new LinkedList<Shark>();

			//큐가 빌 때까지
			while(!Q.isEmpty()) {
				Shark s = Q.poll();
		
				int speed = s.speed;
				int dir = s.dir;
				int size = s.size;
				int nx = s.row;
				int ny = s.col;
				while(speed > 0) {
					
					nx += dx[dir];
					ny += dy[dir];
					//범위를 벗어나는가?
					if(nx < 1 || nx > R || ny < 1 || ny > C) {

						//원위치
						nx-=dx[dir];
						ny-=dy[dir];
                        
						//방향바꾸기
						if(dir==1) dir=2;
						else if(dir==2) dir=1;
						else if(dir==3) dir=4;
						else if(dir==4) dir=3;
						
						continue;
					}
					speed--;
					
				}
				//이미 해당자리로 이동한 상어가 있나?
				if(afterMap[nx][ny]>0) {
					// 지금 상어의 크기가 더 큰가?
					if(afterMap[nx][ny]<size) {
						while(!afterQ.isEmpty()) {
							Shark sk = afterQ.poll();
							if(sk.row==nx && sk.col==ny) {
//								System.out.println("잡아먹었다!");
								afterMap[nx][ny]=size;
								break;
							}
							afterQ.add(sk);
						}
						afterQ.add(new Shark(nx,ny,s.speed,dir,size));
					} else {
//						System.out.println("잡아먹혔다!");
					}
				} else {
					afterQ.add(new Shark(nx,ny,s.speed,dir,size));
					afterMap[nx][ny] = size;
				}
				
			}
			
			//상어가 이동한 내용들로 다시 현행화
			Q = afterQ;
			map = afterMap;
		}
		
	}
	
}

class Shark {
	
	int row;
	int col;
	int speed;
	int dir;
	int size;
	
	public Shark(int r,int c, int s, int d ,int z) {
		this.row= r;
		this.col= c;
		this.dir = d;
		this.speed = s;
		this.size = z;
	}
}

 

상어 이동 전, 이동 후를 관리하기 위해서 큐와 map을 2개로 관리했더니

시간초과 나기 직전의 코드로 맞았다..^^;; 뭐 맞은건 맞은거니깐 헤헤...

다른 사람들 코드를 보니 시간초과를 피하기위해서 speed 부분을 나머지 연산을 통해 계산하여 최대한 while반복을 줄이곤 했다.

ex) 방향이 남북/동서냐에 따라 R와 C를 기준으로 연산

speed%=(R-1)*2; or speed%=(C-1)*2;

이렇게 연산하면.... 끝까지 갔다가 원위치로 돌아오는만큼의 반복문을 줄여줄 수 있다.

 

평일 퇴근후에는 알고리즘으로 머리를 말랑하게 해보자고 호기롭게 도전했다가 몇시간동안 끙끙댔다..

와플먹으러 이만,,