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;
}
}
}
}