[백준] 17143 - 낚시왕 (JAVA)

개츠비·2023년 4월 30일

목록 보기

67/84

소요시간 : 4시간
문제 사이트 : 백준
문제 수준 : 골드 1
문제 유형 : 구현, 시뮬레이션
다른 사람의 풀이를 참고 했는가 ? : X
문제 링크 : https://www.acmicpc.net/problem/17143
푼 날짜 : 2023.04.30

1. 사용한 자료구조 & 알고리즘

구현, 시뮬레이션, 큐

2. 사고과정

처음에 문제를 보고 이게 왜 골드1이지 ? 라고 생각했다.
그냥 문제에 있는 전체를 구현하는데 한 30-40분 걸렸다.
그리고 제출했는데 시간초과가 났다.
시간 초과는 물고기들을 이동시키는데 1칸씩 이동시키는 데에서 나게 되는 것이다.
어떻게 하면 시간을 줄일 수 있을까 생각해봤는데
문제를 푼지 1시간째에 접어들어서 나머지 연산으로 이를 해결할 수 있겠다고 생각했다.

나머지 연산의 조건을 생각해내기가 쉽지 않았다.
여기서 3시간을 썼다.

3. 풀이과정

현재 위치에서 낚시해서 가장 가까운 물고기 1마리를 제거한다.
물고기들이 이동하는데, 벽에 부딪히면 반대 방향으로 가야했다.

여기서 나머지 연산을 활용해서 시간을 줄일수 있다.
여기서 나머지는 예를 들어 5개의 칸이 있을 때, 내가 6칸을 갔다면 5%6으로 1이 나오는 것이 아닌, 방금 왔던 방향으로 다시 돌아가는 형태이다. 그렇기에 5의 길이가 있다면
(<1,2,3,4,5> , <1,2,3,4,5> , <1,2,3,4,5> ....) 의 형태가 아닌
(<1,2,3,4,5,4,3,2> , <1,2,3,4,5,4,3,2> , <1,2,3,4,5,4,3,2> ) 의 형태로 반복되는 형태이다.그렇기에 <1,2,3,4,5,4,3,2> 의 배열을 구한다. 내가 우측으로 가는지, 좌측으로 가는지는 이 배열을 통해서 구할 수 있다.

물고기들의 다음 좌표의 위치를 구한 후, 바로 이동시키는 것이 아닌, 그 좌표를 queue에 담는다. 원래 물고기가 있던 위치는 0으로 만든다.
queue 에서 Poll하면서 그 만약 현재 내 물고기의 size가 그 좌표에 있던 물고기의 size보다 크면, 갱신시킨다. 물고기가 없는 자리에서는 그 size가 0이고, 물고기의 최소 size가 1이니, 물고기가 없는 경우에도 같은 방법으로 처리할 수 있다.

4. 소스코드

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

public class Main{
	static int shark[][][];
	static int dy[]= {0,-1,1,0,0};
	static int dx[]= {0,0,0,1,-1};
	static Integer temp1[];
	static Integer temp2[];
	static int sum = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		StringTokenizer st;

		st=new StringTokenizer(br.readLine());
		int R=Integer.parseInt(st.nextToken());
		int C=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());
		shark=new int[R+1][C+1][3];
		func();

		for(int i=0;i<M;i++) {
			st=new StringTokenizer(br.readLine());
			int r=Integer.parseInt(st.nextToken());
			int c=Integer.parseInt(st.nextToken());
			int s=Integer.parseInt(st.nextToken());
			int d=Integer.parseInt(st.nextToken());
			int z=Integer.parseInt(st.nextToken());
			shark[r][c][0]= s;
			shark[r][c][1]= d;
			shark[r][c][2]= z;

		}






		for(int i=1;i<=C;i++) {
			fishing(i);
			moveShark();
		}

		System.out.println(sum);


	}
	public static void fishing(int now) { //낚시한다. 가장 가까운 물고기를 제거한다.

		for(int i=1;i<shark.length;i++) {

			if(shark[i][now][2]>0) {
				sum += shark[i][now][2];
				shark[i][now][0] =0;
				shark[i][now][1] =0;
				shark[i][now][2] =0;
				break;
			}

		}

	}

	public static void moveShark() { //상어들이 이동한다.
		Queue<Integer[]> queue=new LinkedList<>();

		for(int i=1;i<shark.length;i++) {
			for(int j=1;j<shark[0].length;j++) {
				if(shark[i][j][2]>0) {
					Integer moved[] = nextShark(i,j,shark[i][j][0],shark[i][j][1],shark[i][j][2]);
					queue.add(moved);
					shark[i][j][0] = 0;
					shark[i][j][1] = 0;
					shark[i][j][2] = 0;
				}
			}
		}

		while(!queue.isEmpty()) {
			Integer temp[]=queue.poll();
			int nowY=temp[0];
			int nowX=temp[1];
			int s=temp[2];
			int d=temp[3];
			int z=temp[4];
			if(z>shark[nowY][nowX][2]) {
				shark[nowY][nowX][0]=s;
				shark[nowY][nowX][1]=d;
				shark[nowY][nowX][2]=z;
			}
		}



	}
	//다음 상어의 위치,방향을 구한다.
	public static Integer[] nextShark(int r,int c,int s,int d,int z) {


		if(d==1||d==2) {
			if(d==1) 
				r+= temp1.length-(2*(r-1));
			r += s;

			if((r-1)/((shark.length-2))%2!=0) d = 1;
			else d = 2;

			r%=(temp1.length);
			r--;
			if(r==-1) r = temp1.length-1;
			r = temp1[r];	
		}

		else {
			if(d==4) 
				c+=temp2.length-(2*(c-1));
			c +=s;
			if((c-1)/((shark[0].length-2))%2!=0) d = 4;
			else d = 3;

			c%=(temp2.length);
			c--;
			if(c== -1) c=temp2.length-1;
			c = temp2[c];

		}

		Integer arr[]= {r,c,s,d,z};

		return arr;
	}

	//물고기들이 가로, 세로에서 이동하는 방향을 구한다.
	//(1,2,3,4) 라면 물고기는 (<1,2,3,4,3,2>,<1,2,3,4,3,2> ....) 의 형태로 이동한다.
	//<1,2,3,4,3,2> 를 구하는 메소드이다.
	public static void func() {
		int cnt1=shark.length-2;
		int cnt2=shark[0].length-2;

		temp1=new Integer[shark.length+shark.length-4];
		temp2=new Integer[shark[0].length+shark[0].length-4];

		for(int i=0;i<shark.length-1;i++) 
			temp1[i] = i+1;
		for(int i=0;i<shark[0].length-1;i++)
			temp2[i] = i+1;

		for(int i=shark.length-1;i<temp1.length;i++)
			temp1[i]=cnt1--;
		for(int i=shark[0].length-1;i<temp2.length;i++)
			temp2[i]=cnt2--;

	}



}