[백준 - 17143] 골드2 - 낚시왕

www.acmicpc.net/problem/17143

17143번: 낚시왕

1. 유형

시뮬레이션, 우선순위 정렬, 깊은 복사

 

2. 풀이

• 크기순으로 내림차순 정렬
• 하나씩 탐색하면서 시뮬레이션 돌린다

처음 풀이는 시간초과가 났다. 싸이클을 생각해주지 않아서 이다. 

		for (int i = 0; i < sharks.length; i++) {
			if(sharks[i].d <2) {
				sharks[i].s%=rcycle;
			}else {
				sharks[i].s%=ccycle;
			}
		}

위 코드를 넣어서 불필요한 반복을 줄여줘서 시간초과를 해결했다.

 

3. 코드

package 구현.삼성역태;

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class back_17143낚시왕 {
	static int dr[] = {-1,1,0,0};//위 아래
	static int dc[] = {0,0,1,-1};//오른 왼
	static int opp[] = {1,0,3,2};
	static class Shark implements Comparable<Shark>{
		int r,c,s,d,z;//row, col, 속력, 방향, 크기
		public Shark(int r, int c, int s, int d, int z) {
			this.r = r;
			this.c = c;
			this.s = s;
			this.d = d;
			this.z = z;
		}
		@Override
		public int compareTo(Shark o) {
			return o.z - this.z;
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int r = sc.nextInt();
		int c = sc.nextInt();
		int m = sc.nextInt();//상어수
		int map[][] = new int[r][c];
		int rcycle = r*2-2;
		int ccycle = c*2-2;
		Shark sharks[] = new Shark[m];

		for (int i = 0; i < sharks.length; i++) {//상어의 종류
			sharks[i]= new Shark(sc.nextInt()-1, sc.nextInt()-1, sc.nextInt(), sc.nextInt()-1, sc.nextInt());
		}
		for (int i = 0; i < sharks.length; i++) {
			if(sharks[i].d <2) {
				sharks[i].s%=rcycle;
			}else {
				sharks[i].s%=ccycle;
			}
		}
		Arrays.sort(sharks);
		for (int i = 0; i < sharks.length; i++) {//상어의 종류
			map[sharks[i].r][sharks[i].c] = i+1;
		}
		int ans=0;
		for (int pos = 0; pos < c; pos++) {//사람 이동
			for (int i = 0; i < r; i++) {
				if(map[i][pos]!=0) {
					ans+=sharks[map[i][pos]-1].z;//상어 크기 더해준다
					sharks[map[i][pos]-1].d=-1;//상어 죽음
					map[i][pos]=0;//원상복귀
					break;
				}
			}//잡을거 탐색
			//상어이동
			int temp_map[][] = new int[r][c];
			for (int i = 0; i < sharks.length; i++) {
				if(sharks[i].d==-1) //죽은 상어
					continue;
				//속력만큼 이동
				//현 좌표
				int cr = sharks[i].r;
				int cc = sharks[i].c;
				int cd = sharks[i].d;
				int cs = sharks[i].s;
			
				for (int j = 0; j < sharks[i].s; j++) {
					int nr = cr+dr[cd];
					int nc = cc+dc[cd];
					//이탈한경우에 반대방향바꾸고 현좌표에서 반대로 간다
					if(nr<0 || nr>=r || nc<0 ||nc>=c) {
						cr = cr - dr[cd];
						cc = cc - dc[cd];
						cd = opp[cd];
					}else {//이탈 안했음
						cr = nr;
						cc = nc;
					}
				}//속도끝남
				//빈곳이 아니라 다른 상어가 있다
				if(temp_map[cr][cc] !=0) {
					//현 상어를 죽이자
					sharks[i].d = -1;
				}else {
					//그런가 아니라면 갱신
					temp_map[cr][cc] = i+1; //다음좌표 상어 갱신
					sharks[i].r = cr;
					sharks[i].c = cc;
					sharks[i].d = cd;
				}
			}
			for (int i = 0; i < r; i++) {
				for (int j = 0; j < c; j++) {
					 map[i][j] = temp_map[i][j];
				}
			}	
		}//사람 이동끝
		System.out.println(ans);
	}
}