BOJ- 17143 ) 낚시왕

 

... ( 생략 ) 

---

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

17143번: 낚시왕

 

---

낚시꾼이 이동하면서 열에서 가장가까운 물고기를 잡아가면서 답을 구하는 시뮬레이션 문제이다.

 

각 물고기마다 이동방향,속력,크기의 값을 가지고 물고기가 한곳에 두마리 이상 놓이면 크기가 가장큰 물고기가

 

다른 물고기를 먹는다.

 

처음에 그냥 Map을 3차원 배열로 설정하고 y x 좌표에 방향,속력,크기의 정보를 넣어주고 

Copy map으로 이동정보를 적어두고 Map에 덮어 씌우는식으로 진행하려다가,

 

좌표만 따로 큐에 넣어서 처리를 하는편이 좋다고 생각했다.

 

최악의 경우 100X100에 한칸에 int형 3개의 정보가 담기고, Map의 크기를 잡는데에 120K가 소모되고,

 

Copy_Map도 120K를 잡고 최악에 100번을 복사하기 때문에 잘못하면 시간초과나 메모리초과가 날 수도 있지 않을까?

 

생각했었는데 한번에 통과되었다.

 

딱히 포함하는 Wrapper Class Type이 다르지 않다면 3,4차원 배열을 이용해야겠다.

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int map[][][]= new int[r+1][c+2][3];
		int Copy_map[][][]= new int[r+1][c+2][3];
		int dirx[] = {0,0,0,1,-1};
		int diry[] = {0,-1,1,0,0};
		int res=0;
		ArrayDeque<int []> Coordi= new ArrayDeque<>();
		ArrayDeque<int []> Copy_Coordi= new ArrayDeque<>();
		for(int index = 0 ; index < m ; index++) {
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			Coordi.add(new int[] {y,x});
			map[y][x][0] = Integer.parseInt(st.nextToken());
			map[y][x][1] = Integer.parseInt(st.nextToken());
			map[y][x][2] = Integer.parseInt(st.nextToken());
		}
		for(int person = 1 ; person < c+1 ; person++) {
			//이동완료
			//열에서 가장 가까운 상어를 잡음, 없다면 상어의 이동으로 넘어감
			for(int row = 1 ; row < r+1 ; row++) {
				if(map[row][person][2] != 0) {
					// 가장 가까운 상어를 발견
					res +=map[row][person][2];
					map[row][person][2] = 0;
					break;
				}
			}
			
			// 상어이동
			while(!Coordi.isEmpty()) {
				int now[] = Coordi.poll();
				int y = now[0], x = now[1];
				if(map[y][x][2]==0) continue;
				int time = map[y][x][0];
				int direction = map[y][x][1];
				int size = map[y][x][2];
				int ny , nx;
				for(int index = 0 ; index < time ; index++) {
					ny = y + diry[direction];
					nx = x + dirx[direction];
					if(ny == r+1 ||  ny == 0 || nx ==0 || nx == c+1) {
						if(direction ==1) direction =2;
						else if(direction==2) direction =1;
						else if(direction==3) direction =4;
						else if(direction==4) direction =3;
						y += diry[direction];
						x += dirx[direction];
					}
					else {
						y = ny ; x = nx;
					}
					
				}
				
				if(Copy_map[y][x][2] == 0) {
					Copy_map[y][x][0] = time;
					Copy_map[y][x][1] = direction;
					Copy_map[y][x][2] = size;
					Copy_Coordi.add(new int[] {y,x});
				}
				else {
					if(Copy_map[y][x][2] < size) {
						Copy_map[y][x][0] = time;
						Copy_map[y][x][1] = direction;
						Copy_map[y][x][2] = size;
						Copy_Coordi.add(new int[] {y,x});
					}
				}
			}
			while(!Copy_Coordi.isEmpty())Coordi.add(Copy_Coordi.poll());
			
			for(int z = 1 ; z < r+1 ; z++) {
				for(int y = 1 ; y < c+1 ; y++) {
					for(int x = 0 ; x <3 ; x++) {
						map[z][y][x] = Copy_map[z][y][x];
						Copy_map[z][y][x] = 0;
					}
				}
			}
		}
		System.out.println(res);
	}
}

---