Problem Solving/Baekjoon

[백준/JAVA] 17143 - 낚시왕

jihyeon99 2023. 8. 26. 12:32

[문제 포인트]

1) 상어의 이동을 어떻게 처리할까? (상어를 1번씩 이동시키면 약 O(10^9)으로 시간초과ㅠㅠ)

다시 같은 방향 +제자리로 올때까지 얼마나 걸리는가? => 이 시간이  반복되는 크기 임!!! 

즉 상어를 1번씩 반복하며 모두 이동시키는게 아닌,   시간이동 을 통해 이동시간 단축시킬 수 있음!!

 %연산을 이용 해서 줄여주면, 시간 ↓ : 상↔하는 %2*(row-1)을 이용하고, 좌↔우는 %2*(col-1)을 이용함

 

2) 배열의 인덱스를 벗어났을때 이동방향을 어떻게 바꿀까?

방향(dir)을 -1해서 임시 보정 : 상(0), 하(1), 우(2), 좌(3)

해당 방향(dir)을  1과 XOR연산(^= 1) 하면  상↔하 또는 좌↔우로 바뀜

다시 방향(dir)을 +1해서 보정한 값 되돌림 : 상(1), 하(2), 우(3), 좌(4)

 

[문제 풀이]

- 내풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
	static int[][] map; // 맵정보(해당 칸에 상어가 몇마리 있는지)
	static int n; // 행크기
	static int m; // 열크기
	static int nshark; // 상어의 수
	static int result; // 잡은 상어 크기의 합
	// 방향벡터(제자리,상,하,우,좌)
	static int[] dx = {0,-1,1,0,0};
	static int[] dy = {0,0,0,1,-1};
	
	static Map<Integer,int[]> sharkInfo = new HashMap<>(); // 상어 정보 : x, y, speed, dir, size
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken()); // 행크기
		m = Integer.parseInt(st.nextToken()); // 열크기
		nshark = Integer.parseInt(st.nextToken()); // 상어의 수
		
		// 맵 생성하기
		map = new int[n][m];
		
		// 상어 정보 입력받기
		for(int i=1; i<=nshark; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken())-1; // x 좌표
			int y = Integer.parseInt(st.nextToken())-1; // y 좌표
			int speed = Integer.parseInt(st.nextToken()); // 속력
			int dir = Integer.parseInt(st.nextToken()); // 이동방향
			int size = Integer.parseInt(st.nextToken()); // 크기
					
			sharkInfo.put(i, new int[] {x, y, speed, dir, size}); // 맵에 해당 정보 넣어줌(i는 상어 구분하는 키값)
			map[x][y] = i; // 해당 칸에 해당 번호(i)에 해당하는 상어가 있다고 표시
		}
		
		// 만약 상어 0마리라면 -> 바로 종료
		if(nshark == 0) {
			System.out.println(result);
			return;
		}
		
		// step 1 : 낚시왕 오른쪽 1칸씩 이동하면서
		for(int c=0; c<m; c++) {
			// step 2 : 낚시왕의 열에 있는 가장 가까운 상어 잡음 
			int row = findShark(c); // 해당 열에서 가장 가까운 상어의 행 위치
			if(row != -1) { // 상어가 존재한다면(-1이면 존재하지 x)
				int key = map[row][c]; // 해당 상어의 key값 구함
				result += sharkInfo.get(key)[4]; // 해당 상어의 크기 더함
				
				// 해당 위치의 상어를 잡음
				sharkInfo.remove(key); // 맵에서 제거
				map[row][c] = 0; // 배열에서 없어졌다 표시
			}		
			
			// step 3 : 상어 이동
			moveShark();
		}

		System.out.println(result);
	}
	
	// 상어 이동하는 함수
	static void moveShark() {
		int[][] resultmap = new int[n][m]; // 나중에 복사할 배열(원배열은 그대로 놔둠)
		// 2차원 배열을 순회하며
		for(int r=0; r<n; r++) {
			for(int c=0; c<m; c++) {
				if(map[r][c] != 0) { // 상어가 존재한다면(상어 고유 키값 존재하면)
					int key = map[r][c]; // 현재 상어의 키값
					int dir = sharkInfo.get(map[r][c])[3]; // 현재 상어의 방향
					int speed = 0; // 현재 상어의 속력
					// 상하 방향이라면
					if(dir == 1 || dir == 2) {
						speed = sharkInfo.get(map[r][c])[2]%(2*n-2); // 현재 상어의 속력
					}
					// 우좌 방향이라면
					else if(dir == 3 || dir == 4) {
						speed = sharkInfo.get(map[r][c])[2]%(2*m-2); // 현재 상어의 속력
					}				
					
					int nextx = r; // 이동한 상어의 x좌표
					int nexty = c; // 이동한 상어의 y좌표
					
					// 1개의 상어가 이동
					for(int i=0; i<speed; i++) {
						int tempx = nextx + dx[dir]; // 상어가 이동할 x좌표
						int tempy = nexty + dy[dir]; // 상어가 이동할 y좌표
						
						// 배열 인덱스 넘어간다면 -> 방향전환
						if(tempx<0 || tempx>=n || tempy<0 || tempy>=m) { 
							// 방향 전환
							if(dir%2 == 1) dir+=1; // 상/우라면 -> 하/좌로
							else if(dir%2 == 0) dir-=1; // 하/좌라면 -> 상/우로
							// 다시 바뀐 방향으로 설정
							tempx = nextx + dx[dir];
							tempy = nexty + dy[dir];
						}
						// 이동한 상어의 좌표 업데이트
						nextx = tempx;
						nexty = tempy;
					}
					
					// 이미 해당칸에 다른 상어 존재하는 경우
					if(resultmap[nextx][nexty] != 0) { // resultmap에 상어 존재한다면(상어 고유키값 0아니라면)
						int cur = sharkInfo.get(key)[4]; // 현재 새로 이동한 상어의 크기
						int next = sharkInfo.get(resultmap[nextx][nexty])[4]; // 원래 있던 상어의 크기
						if(cur > next) { // 이동한 상어 크기 > 원래 있던 상어 크기라면
							sharkInfo.remove(resultmap[nextx][nexty]); // 원래있던 상어 맵에서 제거
							resultmap[nextx][nexty] = 0; // 배열에서 없어졌다 표시
						}
						else { // 이동한 상어 크기 < 원래 있던 상어 크기라면
							sharkInfo.remove(key); // 이동한 상어 맵에서 제거	
							continue; // 상어 정보 업데이트 없이 바로 다음 반복문으로
						}
					}
					
					// 상어 실제로 이동 및 정보 업데이트
					resultmap[nextx][nexty] = key; // 상어 실제로 이동
					sharkInfo.get(key)[0] = nextx; // 이동한 상어 x좌표 업데이트
					sharkInfo.get(key)[1] = nexty; // 이동한 상어 y좌표 업데이트
					sharkInfo.get(key)[3] = dir; // 이동한 상어 이동방향 업데이트
				}
			}
		}
		
		// 임시배열(resultmap)을 원배열(map)에 복사
		for(int i=0; i<n; i++) {
			map[i] = Arrays.copyOf(resultmap[i], m);
		}
	}		
	
	// 해당 열에서 가장 가까운 상어의 행위치 찾음
	static int findShark(int col) {
		for(int r=0; r<n; r++) {
			if(map[r][col] != 0) return r;
		}
		return -1;
	}
}

- 다른사람 풀이1

public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	
	int R = Integer.parseInt(st.nextToken()); // 격자판 행
	int C = Integer.parseInt(st.nextToken()); // 격자판 열
	int M = Integer.parseInt(st.nextToken()); // 상어의 수
	
	int answer = 0;
	int[][][] arr = new int[R][C][3];
	
	int[] dr = {-1, 1, 0, 0}; // 위, 아래, 오른쪽, 왼쪽
	int[] dc = {0, 0, 1, -1}; // 위, 아래, 오른쪽, 왼쪽
	
	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()); // 이동 방향 (1=위, 2=아래, 3=오른쪽, 4=왼쪽)
		int z = Integer.parseInt(st.nextToken()); // 크기
		arr[r][c][0] = s; // 속력
		arr[r][c][1] = d; // 이동방향
		arr[r][c][2] = z; // 크기
	}
		
	// 각 초마다 0열부터 C - 1열까지 낚시왕이 이동하면서 상어를 잡으려고 시도
	for (int time = 0; time < C; time++) {
		
		for (int i = 0; i < R; i++) { // 땅에서 가장 가까운 상어가 있는지 탐색
			if (arr[i][time][2] > 0) { // 크기가 0보다 크다 => 상어가 존재함.
				answer += arr[i][time][2]; // 상어의 크기 누적
				arr[i][time][0] = arr[i][time][1] = arr[i][time][2] = 0; // 해당 영역의 상어가 사라지도록 세팅
				break; // 상어를 잡았으므로 탐색 중단
			}
		}
			
		int[][][] temp = new int[R][C][3]; // 상어의 이동 결과를 저장할 3차원배열
		
		// 상어의 이동
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (arr[i][j][2] > 0) { // 상어의 크기가 0보다 크다 => 상어가 존재하는 위치!
					
					int count = arr[i][j][0], d = arr[i][j][1] - 1; // count: 상어가 이동할 남은 칸수, d: 상어의 이동방향(0=위,1=아래,2=오른쪽,3=왼쪽)
					if (d == 0 || d == 1) { // 위나 아래방향일때 (R - 1) * 2번 움직이면 다시 원래자리와 원래방향으로 돌아온다. 따라서 연산횟수 줄이기 위해 나머지만 취해줌
						count %= (R - 1) * 2;
					} else if (d == 2 || d == 3) { // 오른쪽이나 왼쪽방향일때 (C - 1) * 2번 움직이면 다시 원래자리와 원래방향으로 돌아온다. 따라서 연산횟수 줄이기 위해 나머지만 취해줌
						count %= (C - 1) * 2;
					}
					int r = i, c = j; // 상어의 현재 위치
					while (count > 0) { // 상어가 속도만큼의 칸을 이동하기 전까지 반복
						if ((d == 0 && r == 0) || (d == 1 && r == R - 1) || (d == 2 && c == C - 1) || (d == 3 && c == 0)) {
							// 위방향인데 0행인경우, 아래방향인데 R-1행인경우, 오른쪽방향인데 C-1열인경우, 왼쪽방향인데 0열인경우
							// 방향 반대방향으로 바꿔줌
							d ^= 1; // 1비트 자리를 xor 연산해주면 위<->아래, 오른쪽<->왼쪽 방향전환을 쉽게 할수있다.
						}
						r += dr[d]; // 상어의 위치 이동
						c += dc[d]; // 상어의 위치 이동
						count--; // 상어의 이동할수 있는 남은 칸수 1감소
					}
						
					if (arr[i][j][2] > temp[r][c][2]) { // 상어의 이동결과, 해당위치에 있는 상어의 크기보다 현재이동시킨 상어의크기가 더 클경우 
						temp[r][c][0] = arr[i][j][0]; // 상어의 속력
						temp[r][c][1] = d + 1; // 상어의 이동방향(-1보정시켜줬던거 다시 1더해서 복구)
						temp[r][c][2] = arr[i][j][2]; // 상어의 크기
					}
				}
			}
		}
			
		arr = temp; // 이동결과의 상태로 덮어씌움

	}
		
	System.out.println(answer);
}

- 다른사람 풀이2

/**
 * <단순구현>
 * - 상어가 거꾸로 가는 경우(상, 좌) 인덱스를 일일히 교정하면 비효율적임
 * - 모듈러 연산만으로 상어의 현재 위치 쉽게 구할 수 있도록 인덱스 사이클 배열을 생성
 * 	- 예) R=4 -> [0, 1, 2, 3, 2, 1]
 * 	- 상어 위치 최초 1회 교정 후에는 상행은 하행처럼, 좌행은 우행처럼 똑같이 쓸 수 있음
 * 	- 단, 지도에 상어 위치 저장 시에는 사이클 배열에 저장된 인덱스로 변경하기
 */
public class Main {
	static int R, C, M, answer = 0;
	static Shark[] sharks;
	static Shark[][] map;
	static int[] rows, cols;
	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());
		// 사이클 만들기
		rows = new int[R*2-2];
		cols = new int[C*2-2];
		for(int i = 0; i < R; i++) {
			rows[i] = i;
		}
		int cnt = R-2;
		for(int i = R; i < rows.length; i++) {
			rows[i] = cnt--;
		}
		for(int i = 0; i < C; i++) {
			cols[i] = i;
		}
		cnt = C-2;
		for(int i = C; i < cols.length; i++) {
			cols[i] = cnt--;
		}
		
		// 상어 정보 받기
		sharks = new Shark[M];
		map = new Shark[R][C];
		for(int m = 0; m < M; m++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			Shark s = new Shark(r, c, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			sharks[m] = s;
			map[r-1][c-1] = s;
		}
		
		// 열 수 만큼 반복
		for(int c = 0; c < C; c++) {
			get(c); // 낚시
			move(); // 상어 이동
			eat(); // 상어끼리 잡아먹기
		}
		
		System.out.println(answer);
	}
	
	/**
	 * 상어 이동
	 */
	static void move() {
		for(Shark s : sharks) {
			if(s.dead) { // 죽은 상어
				continue;
			}
			
			if(s.d <= 2) { // 세로 이동
				s.r = (s.r+s.s) % rows.length;
			}else { // 가로 이동
				s.c = (s.c+s.s) % cols.length;
			}
		}
	}
	/**
	 * 상어 잡아먹기
	 */
	static void eat() {
		map = new Shark[R][C];
		for(Shark s : sharks) {
			if(s.dead) { // 죽은 상어
				continue;
			}
			int row = rows[s.r]; // 실제 인덱스로 변경
			int col = cols[s.c];
			
			if (map[row][col] == null) { // 빈칸
				map[row][col] = s;
			}
			else if(map[row][col].z < s.z) { // 내가 더 큼 -> 기존 상어 잡아먹기
				map[row][col].dead = true;
				map[row][col] = s; // 바꾸기
			}
			else { // 내가 더 작음 -> 잡아먹힘
				s.dead = true;
			}
		}
	}
	
	/**
	 * 낚시왕이 상어 잡기
	 */
	static void get(int col) {
		for(int row = 0; row < R; row++) {
			if(map[row][col] != null) {
				map[row][col].dead = true;
				answer+=map[row][col].z;
				break; // 가장 가까운거 잡은 후에는 다음 열로 이동
			}
		}
	}
	
	static class Shark {
		int r, c, s, d, z;
		boolean dead = false;
		
		public Shark(int r, int c, int s, int d, int z) {
			this.r = r-1; // 행
			this.c = c-1; // 열
			this.s = s; // 속도
			this.d = d; // 이동방향
			this.z = z; // 크기
			
			changeCoor();
		}
		/**
		 * 사이클에 해당하는 인덱스로 좌표 교정하기
		 * 거꾸로 가는 경우(상, 좌)에 해당
		 */
		void changeCoor() {
			if(this.d == 1) { // 상행 -> r 교정
				this.r = rows.length - this.r;
			}else if(this.d == 4) { // 좌행 -> c 교정
				this.c = cols.length - this.c;
			}
		}
	}
}