[ 백준 / 17143번 ] Gold II - 낚시왕 : solved by JAVA

www.acmicpc.net/problem/17143

17143번: 낚시왕

문제

낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다.

낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다.

1. 낚시왕이 오른쪽으로 한 칸 이동한다.
2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
3. 상어가 이동한다.

상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초이다. 상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동한다.

왼쪽 그림의 상태에서 1초가 지나면 오른쪽 상태가 된다. 상어가 보고 있는 방향이 속도의 방향, 왼쪽 아래에 적힌 정수는 속력이다. 왼쪽 위에 상어를 구분하기 위해 문자를 적었다.

상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있다. 이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.

낚시왕이 상어 낚시를 하는 격자판의 상태가 주어졌을 때, 낚시왕이 잡은 상어 크기의 합을 구해보자.

입력

첫째 줄에 격자판의 크기 R, C와 상어의 수 M이 주어진다. (2 ≤ R, C ≤ 100, 0 ≤ M ≤ R×C)

둘째 줄부터 M개의 줄에 상어의 정보가 주어진다. 상어의 정보는 다섯 정수 r, c, s, d, z (1 ≤ r ≤ R, 1 ≤ c ≤ C, 0 ≤ s ≤ 1000, 1 ≤ d ≤ 4, 1 ≤ z ≤ 10000) 로 이루어져 있다. (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다. d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.

두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다.

출력

낚시왕이 잡은 상어 크기의 합을 출력한다.

 

 하.. 이렇게 코딩 하나 하는데 오래 걸려서 어떻게 살아갈지 모르겠다... 후... 틀리는게 숫자 잘못써서 틀리는데 도데체 어떡하냐.. .. 왜 그렇게 r,c이런거 구별을 못할까...

[ 풀이 코드 ] 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class 낚시왕 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st =new StringTokenizer(br.readLine());
		int R = Integer.parseInt(st.nextToken());
		int RR = 2*(R-1);
		int C = Integer.parseInt(st.nextToken());
		int CC = 2*(C-1);
		int M = Integer.parseInt(st.nextToken());
		int[][] shark = new int[M][5];
		for(int i =0; i < M ;i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken())-1;
			int c = Integer.parseInt(st.nextToken())-1;
			int s = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			if(d>2) {
				s%= CC;
			}else {
				s%=RR;
			}
			int z = Integer.parseInt(st.nextToken());
			shark[i]  = new int[] {r,c,s,d,z};
		}//입력 끝 
		Arrays.sort(shark, (a,b)->(b[4]-a[4]));
		int ans =0; 
		for(int n = 0; n<C;n++) {
			int f =M;
			int min = R;
			for(int m = 0; m<M ; m++) {
				if(shark[m][1]==n && shark[m][0]<min) {
					f = m;
					min = shark[m][0];
				}
			}
			if(f!=M) {
				ans+=shark[f][4];
				M--;
			}
			for(int i =f ; i<M; i++) {
				shark[i] = shark[i+1];
			}// 낚시 했으면 한마리 지우고, 움직일 거
			boolean[][] v = new boolean[R][C];// 상어가 지금 자리에 있냐 없냐 
			for(int i= 0; i< M; i++) {// 물고기 배열 또 돌기 
				int r= shark[i][0];
				int c = shark[i][1];
				int s = shark[i][2];
				int d = shark[i][3];
				switch(d) {
				case 2:
					r+=s;
					if(r>=R && r<=RR) {
						r = RR-r;
						d = 1;
					}else if(r>RR) {
						r-=RR;
					}
					break;
				case 1:
					r-=s;
					if(r<0 && r>-R) {
						r = Math.abs(r);
						d = 2;
					}else if(r<=-R) {
						r = RR+r;
					}
					break;
				case 3:
					c+=s;
					if(c>=C && c<=CC) {
						c = CC-c;
						d = 4;
					}else if(c>CC) {
						c -=CC;
					}
					break;
				case 4:
					c-=s;
					if(c<0 && c>-C) {
						c = Math.abs(c);
						d = 3;
					}else if(c<=-C) {
						c = CC+c;
					}
					break;
				}
				if(v[r][c]) {
					M--;
					for(int x=i ; x<M; x++) {
						shark[x] = shark[x+1];
					}// 낚시 했으면 한마리 지우고, 움직일 거
					i--;
				}
				else {
					v[r][c] = true;
					shark[i][0] = r;
					shark[i][1] = c;
					shark[i][3] = d;
				}
			}
		}
		System.out.println(ans);
		
	}
}

[ 풀이 ]

 

 이 문제를 풀면서 진짜 고민이 많았다.. 이걸 어떻게 풀지.. 이걸 어떻게 풀지.. 이걸 어떤식으로 선언해 줘야 야 이 문제를 시간초과 안나고 잘 풀수 있을까.. 이렇게 해도 반복, 저렇게 해도 반복인데 도데체 어떡하지..

난리를 치다가 근데 풀기는 풀었다.. 생각보다 효율성 테스트는 적었던 걸로.. 

 

 머릿속으로 이걸 어떤 방법으로 풀어야 하는지를 고민해봐야 풀수 있는 문제같다..

나는 기본적으로 배열을 좋아하는 사람이라 그냥 배열로 풀었다.. 배열이 빠를 거 같기도 했고. 근데 물론 구조체가 빠른거 같다. 이렇게 저렇게...

여기서는 머릿속으로 계산해야하는 것들이 있는데,  

그걸 위해 RR과 CC를 선언해 주었다. 이건 한바퀴 돌아서 제자리 제 방향으로 오는데 걸리는 속도이다. 

속도가 RR이나 CC를 넘으면 그냥 그대로 제자리로 돌아오게 된다.  그러므로 속도는 RR,CC의 나머지로 정해준다. 

그럼 우선 상어 리스트가 만들어진다. 

그리고 여기에서 상어는 자리를 차지하면 z값이 크면 그 순서대로 있게된다, 그래서 정렬을 해주었다. 큰게 미리 그 자리에 있으면, 그 물고기는 버린다. 

ans라는 잡은 물고기 z값들을 더할 거를 정해주고, 

이제 낚시왕이 0~C까지 한칸씩 움직이며 낚시를 한다. 

낚시왕은 f 가 가까운 리스트 순서를 담아줄 값이고, min 이 그 다른 걸 담아둘 값이고, 한다.

 그럼 이제 상어의 배열을 다 돌면서, 낚시왕이 있는 열이면서 행값인 r이 가장 작은걸 찾는다. 

만약 그러한 값이 있으서 f가 M이 아니라면, 

ans에 잡은 물고기의 크기를 더하고, M을 뺀다. 

시간초과가 두려워서 상어를 배열로 선언해 주었으니, 

이후 반복문을 돌면서 값을 지우게 되는데, 사실 ArrayList로 구현하는게 더 빨랐을 수도 있다. 안해봐서 잘 모른다.

그리고 이제 상어의 이동이 시작된다. 

먼저 상어가 그 자리에 있는지 없는지를 확인할 v를 선언해 주고, 

비교를 위해 필요한 값들을 미리 담아준다. 

그리고 스위치 문을 통해 어디로 이동하는지를 확인하게 된다. 

이게 왔다 갔다 하는 값이다 보니까 어떻게 해야 제 위치로 계산되는지 고민이 많았다. 반복해서 돌리면 시간초과가 날거 같고, 

 그리고 나중을 위해서도 이런거 한번 계산해 보는게 좋지, 

이 방법을 유도하기 위해서 

R = 4를 예시로 들면 

 

-6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9

 0 -1 -2 -3 -2 -1 0 1 2 3 2 1 0 1 2 3 

위와 같은 순서로 r+s나 r-s가 구현된다. 

만약 r+s가 3보다 작을 경우는 그냥 그 값을 써도 되고, 

r+s가 3보다 크고 , 6사이라면

r+s 는 RR-r 가 되고, d 의 방향도 반대가 된다. 

r+s가 6보다 크다면 r-=RR이  현재 위치가 된다. 이런식으로 구현을 했다. 

(이전의 s를 조정해서 s는 RR인 2*(4-1)보다 작다. 최대 가 되봐야 3+s는 9이다. ) 

쭉 밑에도 같은 방법으로 계산해서 

값을 넣어주었다. 

그리고 이전에 누군가 그 자리를 차지하 고 있는지 검사해야 한다. 

만약 그 자리에 다른 상어가 있다면, 

M을 하나 없애고, 그 자리에 지금 shark이후의 값들을 채워넣는다. 

만약 그 자리에 상어가 없었다면, 그 상어의 위치를 현재 위치로 바꿔주고, 이 자리는 이 상어가 차지하고 있다를 표현해준다. 

이 반복을 다 하면  ans가 계산되고, 

출력해주면 된다. 

하.. 근데 진짜 너무 오래 걸려서 이래가지고 어떻게 코테보나 싶다..