백준_17143 낚시왕(자바) / 시뮬레이션

시간 & 메모리 제한

문제

입력 & 출력

시뮬레이션을 이용한 풀이

package com.Back;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

public class Back_17143 {
	static int R, C, N;
	static int[][] map = new int[101][101];
	
	static int ans = 0;//이게 구하는 답
	static Map<Integer, Shark> sharks = new HashMap<>();//key:상어크기
	
	static class Shark {
		int x, y, speed, dir, size;

		public Shark(int x, int y, int speed, int dir, int size) {
			this.x = x;
			this.y = y;
			this.speed = speed;
			this.dir = dir;
			this.size = size;//no
		}
	}
	
	public static void main(String[] args) throws Exception{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());//행
		C = Integer.parseInt(st.nextToken());//열
		N = Integer.parseInt(st.nextToken());//상어 수
		
		for (int i = 0; i < N; i++) {//상어수만큼
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int speed = Integer.parseInt(st.nextToken());
			int dir = Integer.parseInt(st.nextToken());
			int size = Integer.parseInt(st.nextToken());
			
			sharks.put(size, new Shark(x, y, speed, dir, size));//size는 모든 상어가 다른값을 가지고 있어서 키로 활용 가능
			map[x][y] = size;//상어의 크기
		}//입력끝
		
		for (int i = 1; i <= C; i++) {//가로로 움직임
			fishing(i);//1.낚시왕이 낚시를 함
			moveShark();//2.상어가 이동			
		}
		
		System.out.println(ans);		
	}

	private static void fishing(int col) {
		//1행부터~ROW(끝까지) 아래로 내려가면서 체크
		for (int i = 1; i <= R; i++) {
			if(map[i][col] != 0) {//상어발견
				ans += map[i][col];//상어 사이즈를 누적
				sharks.remove(map[i][col]);//잡은 상어는 사라짐
				map[i][col] = 0;//그자리에는 더 이상 상어 없어
				return;
			}
		}		
	}
	
	//상어가 자신의 속도만큼 이동. 이동 후 위치가 겹치면 잡아먹기
	private static void moveShark() {
		//d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미
		int[] dx = {0,-1,1,0,0};
		int[] dy = {0,0,0, 1,-1};
		
		int[][] tmp = new int[R + 1][C + 1];
		Queue<Integer> looser = new LinkedList<>();
		
		//모든 상어들에 대해 이동
		for (int key : sharks.keySet()) {
			Shark s = sharks.get(key);
			map[s.x][s.y] = 0;//이동할 꺼니까 원래 자리는 초기화
			
			
			//상어가 가진 속도로 이동
			//이동 전 방향 전환해야하나? 체크
			if(s.dir==1 && s.dir==2) {
				s.speed = s.speed % ((R-1)*2);
			}else if(s.dir==3 && s.dir==4) {
				s.speed = s.speed % ((C-1)*2);
			}
			for (int i = 0; i < s.speed; i++) {
				if(s.dir == 1 && s.x == 1) {//위->아래
					s.dir = 2;
					
				}else if(s.dir == 2 && s.x == R){//아래->위
					s.dir = 1;
					
				}else if(s.dir == 3 && s.y == C){//오른->왼
					s.dir = 4;
					
				}else if(s.dir == 4 && s.y == 1){//왼->오른
					s.dir = 3;
				}
				
				//그리고 이동
				s.x += dx[s.dir];
				s.y += dy[s.dir];
				
			}//상어는 자기 속도만큼 모든 이동을 끝냈음. s.x, s.y에는 새로운 위치 값이 들어 있음
			
						
			//새롭게 움직인 위치에 다른 상어가 있는지
			if(tmp[s.x][s.y] == 0) {
				tmp[s.x][s.y] = s.size;
				
			}else if(s.size > tmp[s.x][s.y] ) {// 지금애가 더 커
				looser.add(tmp[s.x][s.y]);//진 애를 추가 
				tmp[s.x][s.y] = s.size;//이긴애가 그자리에
				
			}else {
				looser.add(s.size);
			}
		}//모든 상어들이 위치 이동하고 싸운 후. tmp배열에 싸움에서 이긴 상어들 위치가 저장되어 있음
		
		//상어들 상태 정리하자! sharks, map ->두군데 모두에 반영해줘야 함.
		//1.sharks에서 진 상어들 삭제
		while(!looser.isEmpty()) {
			sharks.remove(looser.poll());//현재까지 살아남은 상어들 정보가 map에 저장되어 있음
		}
		
		//2.map에는 이긴 상어들 표시
		for (int key :sharks.keySet()) {
			Shark s = sharks.get(key);
			map[s.x][s.y] = tmp[s.x][s.y];
		}
	}
}

- 정말 많이 혼동 했던 문제이다.. 상어가 이동을 마친 후에 한 칸에 두 마리 이상 있을 수 있다는 것 때문이였다...

 

한마리의 상어가 이동을 마친 후인가,, 아님 모든 상어가 이동을 마친 후인가 때문에 엄청 고생했던거 같습니다.

 

일단 한마리의 상어가 이동을 마친 후에 겹치는 경우를 따져야 합니다....

 

- 시뮬레이션으로 고기를 잡는 메서드와 이동 후 겹치는 상어에 대한 제거하는 메서드로 나눠서 만들었습니다.

 

- map과 Shark라는 클래스를 동시에 담기 위해서 map을 사용했습니다.

 

- 상어 이동에 관련해서 변경을 하지 않아도 되지만, 저는 가로와 세로의 이동의 경우

 

if(s.dir==1 && s.dir==2) {
		s.speed = s.speed % ((R-1)*2);
	}else if(s.dir==3 && s.dir==4) {
		s.speed = s.speed % ((C-1)*2);
}

  각각의 경우에 따라서 이동량을 줄일 수 있도록 만들었습니다.