[백준] JAVA - 17143. 낚시왕

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

17143번: 낚시왕

생각

단순하게 1초마다 상어를 움직이는 방식으로하면 시간초과가 난다고 알고있었는데 스터디원이 통과가됐다고 해서 저도 이렇게 바꿔서 제출했더니 통과했습니다..

 

원래는 아래와 같은 방법으로 상어의 위치를 계산하도록 했는데 계속 틀렸다고 나왔습니다 어느 부분이 문제인지를 모르겠네요 ㅠㅡㅠ 

 

(추가) 나머지 연산을 사용하여 다시 풀었습니다! 상어가 다시 제자리로 위치하기 까지 2*(크기-1)만큼의 시간이 소요됩니다. 따라서 y방향 움직임일땐 새로운 상어의 속도 = 상어의 속도 % (2*(R-1) 연산을 수행해줍니다.

나머지 연산을 통해 줄여준 주기를 while문을 돌아 상어를 이동시켜줍니다!

int ny = now.y + dy[now.d]*now.s;
int nx = now.x + dx[now.d]*now.s;

//위로 벗어날때 일단 양수로 바꾸고 범위벗어나면 밑에 if에서 한번더처리
if(ny < 0) {
  ny = -ny;
  now.d = 1; //아래 방향
}					
if(ny > R-1) { //아래방향일때 
  int a = ny / (R-1); //몇번 반복했는지 -> 몫이 짝수면 아래 방향 유지, 홀수면 반대로
  int b = ny % (R-1); // 상대 위치
  if(a % 2 == 0) { // 방향 유지
    ny = b;
  }else {
    ny = (R-1) - b;
    now.d = 0; //위로
  }
}

if(nx < 0) {
  nx = -nx;
  now.d = 2;
}				
if(nx > C-1) { // 오른쪽 방향일때
  int a = nx / (C-1);
  int b = nx % (C-1);
  if(a % 2 == 0) {
  	nx = b;
  }else {
    nx = (C-1) - b;
    now.d = 3; //위로
  }
}

 

바꾼 코드는 아래와 같습니다.

 

1. Shark 객체 내부에 move 메소드를 만들어 다음 좌표값으로 y,x 좌표를 갱신시켜줍니다.

 

2. 낚시왕은 가로 너비만큼 반복문을 돌려줘서 해당 열에 있는 상어중 가장 가까운 상어를 잡도록 했습니다.

 

3. Shark 객체를 임시값으로 받아온다음 해당 좌표를 null로 초기화시켜줍니다. 임시값으로 받아온 Shark를 move() 시켜주기 때문에 원래 좌표에 있는 Shark를 없애줘야하기 때문입니다.

 

4. 이동한 좌표에 상어가 없거나, 상어가 있고 기존에 있던 상어의 무게가 내가 이동시켜준 상어의 무게보다 작으면 가장 큰 상어가 위치하도록 map[ny][nx] = (내가 이동시켜준 상어)를 넣어줍니다.

 

Java Code

package com.java.algorithm;

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

public class BOJ_17143_낚시왕Re {
	static int R,C,M;
	static Shark[][] map;
	static int[] dy = {-1,1,0,0};//위 아래 오른 왼
	static int[] dx = {0,0,1,-1};//위 아래 오른 왼
	
	static class Shark{
		int y,x,s,d,z;
		
		public Shark(int y, int x, int s, int d, int z) {
			super();
			this.y = y;
			this.x = x;
			this.s = s;
			this.d = d;
			this.z = z;
		}
		public void move(int y, int x, int s) {
			int ny = y;
			int nx = x;
			for (int i = 0; i < s; i++) {
				ny += dy[this.d];
				nx += dx[this.d];
				if(ny == -1) {
					ny = 1;
					d = 1;
				}else if (ny == R) {
					ny = R-2;
					d = 0;
				}
				if(nx == -1) {
					nx = 1;
					d = 2;
				}else if(nx == C) {
					nx = C-2;
					d = 3;
				}
			}
			
			this.y = ny;
			this.x = nx;
		}
		@Override
		public String toString() {
			return "Shark [y=" + y + ", x=" + x + ", s=" + s + ", d=" + d + ", z=" + z + "]";
		}
		
	}
	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());
		
		map = new Shark[100][100];
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int y = Integer.parseInt(st.nextToken())-1;
			int x = Integer.parseInt(st.nextToken())-1;
			int s = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken())-1;
			int z = Integer.parseInt(st.nextToken());
			Shark shark = new Shark(y, x, s, d, z);
			map[y][x] = shark;
			
		}

		int cnt = 0;
		Shark backup[][] = new Shark[100][100];
		for (int t = 0; t < C; t++) {
			for (int i = 0; i < R; i++) {
				if(map[i][t] != null) {
					cnt += map[i][t].z;
					map[i][t] = null;
					break;
				}
			}
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C; j++) {
					backup[i][j] = map[i][j];
					map[i][j] = null;
				}
			}
			
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C; j++) {
					Shark now = backup[i][j];
					if(now != null) {
						int y = now.y;
						int x = now.x;
						int s = now.s;
						now.move(y, x, s);
						int ny = now.y;
						int nx = now.x;
						if(map[ny][nx] == null || (map[ny][nx] != null && map[ny][nx].z < now.z)) {
							map[ny][nx] = now;
						}
					}
				}
			}
		}
		
		System.out.println(cnt);
		
	}


}

 

Java Code2 - 나머지 연산으로 다시 풀이

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

public class Main {
	static int R,C,M;
	static Shark[][] map;
	static int[] dy = {-1,1,0,0};//위 아래 오른 왼
	static int[] dx = {0,0,1,-1};//위 아래 오른 왼
	
	static class Shark{
		int y,x,d,s,z;

		public Shark(int y, int x, int s, int d, int z) {
			super();
			this.y = y;
			this.x = x;
			this.s = s;
			this.d = d;
			this.z = z;
		}

		@Override
		public String toString() {
			return "Shark [y=" + y + ", x=" + x + ", d=" + d + ", s=" + s + ", z=" + z + "]";
		}
		
	}
	
	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());
		
		map = new Shark[R][C];
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int y = Integer.parseInt(st.nextToken())-1;
			int x = Integer.parseInt(st.nextToken())-1;
			int s = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken())-1;
			int z = Integer.parseInt(st.nextToken());
			map[y][x] = new Shark(y, x, s, d, z);
		}
		int ans = solve();
		System.out.println(ans);
	}
	
	private static int solve() {
		int total = 0;
		for (int x = 0; x < C; x++) {
			total += catchShark(x); // 상어 잡기
			
			// 상어를 큐에 넣고 이동 -> 큐 초기화 여기서 해줘야 함
			Queue<Shark> q = new LinkedList<Shark>();
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C; j++) {
					if(map[i][j] != null) {
						q.add(map[i][j]);
					}
				}
			}
			//맵도 초기화 -> 이동 후 상어들을 아무것도 없는 map에 넣어야 함
			map = new Shark[R][C];
			
			int size = q.size();
			while(size-- > 0) {
				Shark now = q.poll();
				
				int ny = now.y;
				int nx = now.x;
				int nd = now.d;
				int nz = now.z;	
				int ns = 0;
				if(now.d <= 1) { // y방향 운동
					ns = now.s % (2*(R-1)); // 나머지연산으로 줄여주기
					int tempSpeed = ns;
					while(tempSpeed-- > 0) {
						if(ny == 0 && nd == 0) {
							nd = 1;
						}else if(ny == R-1 && nd == 1) {
							nd = 0;
						}
						ny += dy[nd];
						
					}
				}else { //x방향 운동
					ns = now.s % (2*(C-1)); // 나머지연산으로 줄여주기
					int tempSpeed = ns;
					while(tempSpeed-- > 0) {
						if(nx == 0 && nd == 3) {
							nd = 2;
						}else if(nx == C-1 && nd == 2) {
							nd = 3;
						}
						nx += dx[nd];
					}
				}
				
				if(map[ny][nx] == null) {
					map[ny][nx] = new Shark(ny,nx,ns,nd,nz);
				}else {//이동하려는 좌표에 이미 상어가 있을때 (지금 라운드에 움직인 상어가 위치한것)
					Shark prevShark = map[ny][nx];
					if(prevShark.z < now.z) { // 이동하려는좌표에 있는 기존상어 < 지금 라운드에서 이동한 새로운 상어
						map[ny][nx] = new Shark(ny,nx,ns,nd,now.z);
					}
				}
				
			}//상어 이동 완료
			//print();
		}
		return total;
		
	}
	private static int catchShark(int x) {
		int ans = 0;
		for (int y = 0; y < R; y++) {
			if(map[y][x] != null) {
				ans += map[y][x].z;
				map[y][x] = null; // 잡은 상어 지워주기
				break;
			}
			
		}
		return ans;
	}
	private static void print() {
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				System.out.print(map[i][j]+" ");
			}
			System.out.println();
		}
		System.out.println();
	}
}