[백준] 17143번 낚시왕 (java, 시뮬레이션)

www.acmicpc.net/problem/17143

17143번: 낚시왕

문제자체는 어렵지 않은데 시간초과가 있어서 최적화해줘야한다. 

 

--- 풀이

 

r길이는 2인데 속도가 1000이라면 엄청나게 왔다갔다해야된다. 같은 위치에 있을 경우의 규칙을 찾아야된다.

 

주의할 점은 같은 위치에 있더라도 방향이 반대인 것은 같은 경우가 아니다! 

 

예를 들면 C=5이고 현재 열 번호 1에 있고 우로 움직이는 상어가 있다고 하자

 

열 번호 1 2 3 4 5 인 경우 S=1이면 오른쪽으로 열 번호 2로 갈 것이다. 

 

S=2 => 열 번호 3에 위치

S=3=> 열번호 4에 위치 

S=4 => 열번호 5에 위치

S=6 => 열번호 4에 위치, 방향이 좌로 바뀜!!

 

이 때 S=3인 경우와 6인 경우는 열번호 4에 위치하는 것은 같지만 방향은 반대이다. 이 두 경우는 같은 경우가 아니다.

 

마찬가지로 S=7인 경우도 S=1일 경우와 같은 열에 위치하지만 방향이 반대라서 같은 경우로 볼 수 없다.

S=9 인 경우가 S=1인 경우와 똑같이 방향이 오른쪽이고 열의 위치도 같은 경우이다.

 

그럼 손으로 따라가보면 S=1인 경우와 S=9, S=17, S=25인 경우가 같은 경우라는 것을 알 수 있다. 등차가 8이다.

 

근데 C가 달라지면 등차가 달라진다.

C(행의 길이)가 2, 3, 4인 경우도 시뮬을 돌려보면 등자는 2*(C-1)이다. (종이에 적으면서 하면 이해된다)

 

상어가 위아래로 움직이는 경우 등차는 R(행의길이)로 계산해줘야 된다.

 

최종 위치는 S%(2*(C-1)) 이다. 

 

나머지 연산이라서 최대 움직이는 길이가 한정된다.

 

그 다음에는 실제 S가 움직이는 칸의 수이니 그만큼 for문을 돌리면서 좌표가 넘어가면 방향을 바꿔주면 된다.

 

for (int n = 0; n < s; n++) {// 속도가 1
	int yy=y+ypos[d];
	int xx=x+xpos[d];
	if(xx<0 || yy<0 || xx>=c || yy>=r) {
		// 범위 넘어가면 방향 반대 전환
		if(d==1 || d==2) {
			d=3-d;
		}else {
			d=7-d;
		}
		n--;//방향만 바꿔서 다시 이동
		continue;
	}
	y=yy;
	x=xx;
}

 

 

import java.util.Scanner;

class Shark{
	int num,r,c,s,d,z;

	public Shark(int num,int r, int c, int s, int d, int z) {
		super();
		this.num=num;
		this.r = r;
		this.c = c;
		this.s = s;
		this.d = d;
		this.z = z;
	}
	
	
}

public class Main {
	static int r,c,m;
	static int[][] map;
	static int[] xpos= {0,0,0,1,-1};//위 아래 오른쪽 왼쪽
	static int[] ypos= {0,-1,1,0,0};
	static Shark[] list;
	static int answer;
	static boolean[] isCatched;//해당 상어가 잡혔는가
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		r=sc.nextInt();
		c=sc.nextInt();
		m=sc.nextInt();
		map=new int[r][c];
		list=new Shark[m+1];
		isCatched=new boolean[m+1];
		for (int i = 1; i <= m; i++) {
//			 r c s d z  위치 속력 s 이동방향 d z 크기 
			int y=sc.nextInt()-1;
			int x=sc.nextInt()-1;
			int s=sc.nextInt();
			int d=sc.nextInt();
			int z=sc.nextInt();
			list[i]=new Shark(i,y,x,s,d,z);
			map[y][x]=i; //map에 상어 정보를 저장한다.
		}
		

		
//		//낚시꾼 이동하는 열
		for (int position = 0; position < c; position++) {
			person(position);
			move();
		}
		System.out.println(answer);
	}
	
	private static void person(int position) {
		
		for (int i = 0; i < r; i++) {
			if(map[i][position]!=0) {
				int num=map[i][position];//잡은 상어 번호
				answer+=list[num].z;
				isCatched[num]=true;//잡힘
				break;
			}
		}
		
	}
	
	private static void move() {
		int[][] copy=new int[r][c];	//0
		
		for (int i = 1; i <=m; i++) {
			if(isCatched[i])continue;//잡혀서 없는 상어
			
			int d=list[i].d;
			int y=list[i].r;
			int x=list[i].c;
			//이동하는 칸수 s*d
			int div;
			if(d==1 ||d==2) {
				div=(r-1);
			}else {
				div=(c-1);
			}

			int s=list[i].s%(2*div);// 등차 수열로 같다. // 위치 

			for (int n = 0; n < s; n++) {// 속도가 1
				int yy=y+ypos[d];
				int xx=x+xpos[d];
				if(xx<0 || yy<0 || xx>=c || yy>=r) {
					// 범위 넘어가면 방향 반대 전환
					if(d==1 || d==2) {
						d=3-d;
					}else {
						d=7-d;
					}
					n--;//방향만 바꿔서 다시 이동
					continue;
				}
				y=yy;
				x=xx;
			}
			//방향 갱신해주기 , 상어 정보 업데이트
			list[i].d=d;
			list[i].r=y;
			list[i].c=x;
			// 일단 이동했음 만약에 다른 상어 있는지 확인해준다.
			
			if(copy[y][x]!=0) {//다른 상어 있음
				int other=copy[y][x];
				if(list[i].z>list[other].z) {//내가 더 큼
					copy[y][x]=i;
					isCatched[other]=true;//이 상어는 죽음
				}else {//내가 죽음
					isCatched[i]=true;
				}
			}else {//다른 상어 없음
				copy[y][x]=i;
			}
			
		}
		// map상태 갱신
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				map[i][j]=copy[i][j];
			}
		}

		
	}
	

}