[백준] 17143 낚시왕 (삼성SW역량테스트 기출 문제) -JAVA

 

17143번: 낚시왕 (acmicpc.net)

17143번: 낚시왕

 

풀이

알고리즘 파악

 

시물레이션

 

뭐 복잡한 건 없다. 그냥 구현 문제이다. 

 

구현

 

1. m마리의 상어를 담는 배열과, 상어의 위치를 기록할 2차원 map 배열을 만든다. 

2. 낚시왕은 오른쪽 열로 한 칸씩 전진한다. 그 후 해당 열에서 가장 가까운 상어 한 마리를 잡는다. 잡은 상어는 무게를 더한다.

2. 잡은 상어는 status 상태를 false 로 만들어 죽은것으로 취급한다.(상어가 서로를 잡아먹을 때도 똑같이 한다.) 

3. 상어를 움직이고 위치가 겹칠시 무게가 더 작은놈을 제거한다. 

 

이 문제에서의 핵심은 상어를 움직이는 것이다. 벽을 만난 상어는 방향 전환을 해야 하는데 이것을 잘 구현해야 한다.

단순히 while문을 돌릴시 최대 1000번씩 확인을 해야히기에 대단히 비효율적이다.

이것을 다른 사람들과는 다르게 조금 특이하게(?) 구현했다. 실행속도는 확실히 빠른 편인데 (352ms) 다소 복잡해서 코딩하는 시간은 많이 걸렸다...

 

암튼 나의 구현 방법은

 

1) 상어의 현재 위치에서 속력을 빼 위치를 구한다. 상어가 벽을 벗어나면 2)를 수행하고 아니면 그대로 상어의 위치를 기록한다.

 

2) 벽을 벗어난 상어의 남은 이동거리를 계산한다. 이때 상어는 벽에 위치한다고 가정한다. 남은 이동거리를 해당 열이나 행의 길이-1(반대쪽 끝으로 갈 수 있는 거리)을 나눠서 몫과 나머지를 구한다.  몫은 끝에서 끝으로 가는 편도의 횟수이며, 나머지는 편도 횟수를 제외한 남은 이동거리이다. 편도의 횟수가 짝수이거나 0이면 현재 위치에서 남은 이동거리를 더하고(왕복의 개념), 홀수이면 반대편 끝에서 이동거리를 더한다. 이를 계산해 상어의 위치를 기록한다. 

 

 

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {
	static int r,c,m,answer;
	static int[][] map;
	static Shark[] sharks;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw  =new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		r = Integer.parseInt(st.nextToken());
	    c = Integer.parseInt(st.nextToken());
	    m = Integer.parseInt(st.nextToken());
	    map = new int[r+1][c+1];
	    sharks = new Shark[m+1];
	    for(int i=1; i<=m; i++)
	    {
	    	st = new StringTokenizer(br.readLine()); 
	    	int x = Integer.parseInt(st.nextToken());
	    	int y = Integer.parseInt(st.nextToken());
	    	int s = Integer.parseInt(st.nextToken());
	    	int d = Integer.parseInt(st.nextToken());
	    	int z = Integer.parseInt(st.nextToken());
	    	sharks[i] = new Shark(i,x,y,s,d,z);
	    	map[x][y] = i;
	    }
	    solution();
	    
	    bw.write(Integer.toString(answer));
        bw.flush();
        bw.close();
        br.close();
	}
	
	static void solution()
	{
		for(int i=1; i<=c; i++)
		{
			for(int j=1; j<=r; j++)
			{
				if(map[j][i]!=0)
				{
					sharks[map[j][i]].status = false; //상어 사냥
					answer+=sharks[map[j][i]].z;
					break;
				}
			}
			move_shark();
		}
	}
	
	static void move_shark()
	{
		map = new int[r+1][c+1]; //초기화
		for(int i=1; i<=m; i++)
		{
			Shark shark = sharks[i];
			if(shark.status) //존제
			{	
				int nx=0,ny=0;
				int direc = shark.d;
				if(shark.d==1) //위
				{
					int dist = shark.x -shark.s;
					nx = dist; ny =shark.y;
					if(dist<=0) //벽 뚫음
					{
						dist = Math.abs(dist)+1; //남은 거리
						direc =2; //방향 전환
						int num=dist/(r-1);
						dist%=(r-1);
						
						if(num%2==0) nx = 1+dist; //짝수
						else //홀수
						{
							direc=1; //다시 전환
							nx = r-dist;
						}
					}
				}	
				else if(shark.d==2) //아래	
				{
					int dist = shark.x +shark.s;
					nx = dist; ny =shark.y;
					if(dist>r) 
					{
						dist -= r; //남은 거리
						direc =1; //방향 전환
						int num=dist/(r-1);
						dist%=(r-1);
						
						if(num%2==0) nx = r-dist; //짝수
						else //홀수
						{
							direc=2; //다시 전환
							nx = 1+dist;
						}
					}
				}	
				else if(shark.d==3) //오른쪽	
				{
					int dist = shark.y +shark.s;
					nx = shark.x; ny =dist;
					if(dist>c) 
					{
						dist = dist-c; //남은 거리
						direc =4; //방향 전환
						int num=dist/(c-1);
						dist%=(c-1);
						
						if(num%2==0) ny = c-dist; //짝수
						else //홀수
						{
							direc=3; //다시 전환
							ny = 1+dist;
						}
					}
				}	
				else //왼쪽
				{
					int dist = shark.y -shark.s;
					nx = shark.x; ny =dist;
					if(dist<=0) 
					{
						dist = Math.abs(dist)+1; //남은 거리
						direc =3; //방향 전환
						int num=dist/(c-1);
						dist%=(c-1);
						
						if(num%2==0) ny = 1+dist; //짝수
						else //홀수
						{
							direc=4; //다시 전환
							ny = c-dist;
						}
					}
				}
				shark.x = nx; shark.y = ny;
				shark.d = direc;
				if(map[nx][ny]==0) map[nx][ny] =shark.idx;
				else
				{
					if(sharks[map[nx][ny]].z < shark.z) { sharks[map[nx][ny]].status =false; map[nx][ny] =shark.idx; } //새로운놈이 더 큼
					else shark.status = false; //기존이 더 큼
				}
			}
		}
	}
	static class Shark
	{
	   boolean status;
	   int idx;
	   int x;
	   int y;
	   int s;
	   int d;
	   int z;
	   public Shark(int idx, int x, int y,int s,int d,int z)
	   {
		   this.status= true;
		   this.idx = idx;
		   this.x =x;
		   this.y =y;
		   this.s= s;
		   this.d = d;
		   this.z =z;
	   }
	}
	
}