백준 : 17143

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

17143번: 낚시왕

 

시뮬레이션 문제

이문제는 2차원 ArrayList를 설정해서 물고기가 겹친다는것을 표현해주면 푸는데 문제가없다.

문제는 속도와 방향을주고 1초에 이동햇을때 위치와 d값을 찾는것이다.

 

이때 수식을 그려보면

 

// 1 - ( 1미만값 - 1) 음수일때 오른쪽으로가는 값
// 2*R - (R초과값) R초과일때 왼쪽으로 이동하는 값

를 구할수있다. 매전 값이 맵안에 올때까지 d의 방향을 바꾸어가면서 접근 하면된다.

 

package com.ssay.algo;

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

public class B17143 {
	static int dy[] = { 0, -1, 1, 0, 0 };
	static int dx[] = { 0, 0, 0, 1, -1 };
	// R : 행 , C : 열, M : 상어수
	static int R, C, M;
	static ArrayList<Integer>[][] Map;

	public static class Shark {
		int y;
		int x;
		int s;
		int d;
		int z;

		public Shark(int y, int x, int s, int d, int z) {
			this.y = y;
			this.x = x;
			this.s = s;
			this.d = d;
			this.z = z;
		}
	}

	static Shark[] shark;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());

		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		// r c s d z : s:속력 z:사이즈
		shark = new Shark[M + 1];
		Map = new ArrayList[R + 1][C + 1];

		// i 번째 상어를 mapping
		for (int i = 1; i <= M; i++) {
			st = new StringTokenizer(br.readLine());
			shark[i] = new Shark(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()),
					Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()),
					Integer.parseInt(st.nextToken()));
		}

		// 상어를 mapping
		for (int i = 1; i <= R; i++) {
			for (int j = 1; j <= C; j++) {
				Map[i][j] = new ArrayList<Integer>();
			}
		}

		for (int m = 1; m <= M; m++) {
			Map[shark[m].y][shark[m].x].add(m);
		}

		int Answer = 0;

		// 사람을 한칸식 이동시킨다.
		for (int t = 1; t <= C; t++) {
			// 상어잡기
//			for(int i=1;i<=R;i++) {
//				for(int j=1;j<=C;j++) {
//					if(!Map[i][j].isEmpty()) {
//						System.out.print(shark[Map[i][j].get(0)].z+" ");
//					}else {
//						System.out.print("0 ");
//					}				
//				}
//				System.out.println();
//			}
//			System.out.println();
			
			for (int i = 1; i <= R; i++) {
				if (!Map[i][t].isEmpty()) {
					int eat = Map[i][t].get(0);
					Map[i][t].remove(0);
					Answer += shark[eat].z;
					// 죽은 shark size = 0
					shark[eat].z = 0;
					break;
				}
			}

			// 상어이동
			for (int m = 1; m <= M; m++) {
				// 죽은 상어는 무시
				if (shark[m].z == 0)
					continue;

				int y = shark[m].y;
				int x = shark[m].x;
				int s = shark[m].s;
				int d = shark[m].d;
				int z = shark[m].z;

				// 맵에서 제거
				for(int k=0;k<Map[y][x].size();k++) {
					if(Map[y][x].get(k) == m) {
						Map[y][x].remove(k);
						break;
					}
				}
				


				// R C y x d s 를 이용해서 맵위치 계산
				// 1 - ( 1미만값 - 1) 음수일때 오른쪽으로가는 값
				// 2*R - (R초과값) R초과일때 왼쪽으로 이동하는 값

				y = y + dy[d] * s;
				x = x + dx[d] * s;

				// 범위 안에 있는 값을 벗어나면 ny,nx가 다음에 이동할 값.
				while (!(y >= 1 && y <= R && x >= 1 && x <= C)) {
					// d위치를 반대로 바꾼다.
					if (d == 1)
						d = 2;
					else if (d == 2)
						d = 1;
					else if (d == 3)
						d = 4;
					else if (d == 4)
						d = 3;

					// 벗어난 구역
					if (y < 1) {
						y = 1 - (y - 1);
					} else if (y > R) {
						y = 2 * R - y;
					} else if (x < 1) {
						x = 1 - (x - 1);
					} else if (x > C) {
						x = 2 * C - x;
					}

				}
				
				Map[y][x].add(m);
				shark[m] = new Shark(y, x, s, d, z);
			}

			// 상어이동후 먹기
			
			for(int i=1;i<=R;i++) {
				for(int j=1;j<=C;j++) {
					if(Map[i][j].isEmpty()) continue;
					if(Map[i][j].size() == 1) continue;
					// 두마리 이상 있는거는 가장큰 사이즈의 상어가 먹는다.
					int bigShark = shark[Map[i][j].get(0)].z;
					int num = Map[i][j].get(0);
					// 가장 큰 상어 탐색
					
					for(int k=1;k<Map[i][j].size();k++) {
						if(bigShark < shark[Map[i][j].get(k)].z) {
							bigShark = shark[Map[i][j].get(k)].z;
							num = Map[i][j].get(k);
						}
					}
					
					//이제 bigShark말고 맵에서 다죽이면됨.
					for(int k=0;k<Map[i][j].size();k++) {
						
						if(Map[i][j].get(k) ==num) continue;
						shark[Map[i][j].get(k)].z = 0;
					}
					
					
					Map[i][j].clear();
					Map[i][j].add(num);
					
				}
			}

		}
		
		System.out.println(Answer);

	}

}