BOJ - 낚시왕 17143번 (JAVA)

❓ 문제 - 백준 낚시왕 17143번 - JAVA 풀이법

 

출처 

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

 

 

 

📝 문제해결법

1. 이 문제는 구현으로 풀었다.

• Shark라는 객체 2차원 배열의 map으로 상어를 관리한다.
• 낚시왕이 0열부터 마지막 열까지 이동하면서 낚시를 하고 각 상어는 이동하는데 맞춰서 구현해주면 된다.
• 낚시 하는 부분은 해당 열에서 가장 작은 행부터 차례대로 상어가 존재하는지를 찾아서 낚시 처리한다.
• 상어의 이동 부분 에서는 shark_copy라는 객체 2차원 배열을 만들고 이동하면서 거기에 이동한 상어의 객체를 넣어준다. 만약 이동할 곳인 shark_copy에 이미 상어가 존재한다면 상어의 크기를 비교해서 작은 상어는 제거한다.
• 한 상어의 이동을 처리할 때 s가 매우 큰 범위이므로 while문으로 한 칸씩 이동 처리하면 아슬아슬하게 시간 통과하거나 시간복잡도가 매우 커진다. 
• 따라서 이동 패턴의 반복을 속력이 s일 때 가로로 이동하면 s % (r+r-2), 세로로 이동하면 s % (c+c-2) 로 나누어서 처리한 후 이동처리해준다.
• 가로로 이동할 땐 (r-1) * 2, 세로로 이동할 땐 (c-1)*2 배에 항상 제자리로 돌아오기 때문이다.
• 만약 격자의 범위를 넘어가면 다시 돌아와서 방향을 반대로 바꾼 후 이동처리를 맞춰서 하면 된다.

 

💻 소스코드

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

public class Main_17143 {
	public static int r, c, m;
	public static Shark[][] shark;
	
	public static class Shark {
		int x;
		int y;
		int s;
		int d;
		int z;
		public Shark(int x, int y, int s, int d, int z) {
			this.x = x;
			this.y = y;
			this.s = s;
			this.d = d;
			this.z = z;
		}
	}
	
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = {0, 0, 1, -1};
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		shark = new Shark[r][c];
		
		for(int i=0;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());
			shark[x-1][y-1] = new Shark(x-1, y-1, s, d-1, z);
		}
		
		int ans = 0;
		for(int j=0;j<c;j++) {
			for(int i=0;i<r;i++) {
		
				// 낚시
				if(shark[i][j] != null) {
					ans += shark[i][j].z;
					shark[i][j] = null;
					break;
				}
			}
			
			Shark[][] shark_copy = new Shark[r][c];
			
			// 상어의 이동
			for(int x=0;x<r;x++) {
				for(int y=0;y<c;y++) {
					if(shark[x][y] == null) continue;
					Shark sk = shark[x][y];
					int moving = 0;
					if(sk.d <= 1) {
						moving = (sk.s) % (r+r-2);
					} else {
						moving = (sk.s) % (c+c-2);
					}
					
					int nx = sk.x;
					int ny = sk.y;
					int dir = sk.d;
					while(moving-- > 0) {
						nx += dx[dir];
						ny += dy[dir];
						if(nx < 0 || nx >= r || ny < 0 || ny >= c) {
							nx -= dx[dir];
							ny -= dy[dir];
							if(dir % 2 == 0) {
								dir += 1;
							} else {
								dir -= 1;
							}
							nx += dx[dir];
							ny += dy[dir];
						}
					}
					
					if(shark_copy[nx][ny] != null) {
						if(shark_copy[nx][ny].z < sk.z) {
							shark_copy[nx][ny] = new Shark(nx, ny, sk.s, dir, sk.z);
						}
					} else {
						shark_copy[nx][ny] = new Shark(nx, ny, sk.s, dir, sk.z);
					}
				}
			}
			shark = shark_copy;
			
		}
		
		System.out.println(ans);

	}
	
	public static void print(Shark[][] shark) {
		for(int i=0;i<r;i++) {
			for(int j=0;j<c;j++) {
				System.out.print(shark[i][j] != null?'o':'x');
			}
			System.out.println();
		}
		
	}

}