BOJ 17143번: 낚시왕

문제

문제 바로가기 > BOJ 17143번: 낚시왕

17143번: 낚시왕

 

풀이

문제를 풀 때 중요하다고 느낀 점을 몇가지 적어보겠다.

 

1. 상어 이동 시 편의를 위해, num 배열을 만들고, 해당 상어의 정보(순서)를 저장해 둔다. 

  num[r][c] = i : (r, c) 위치의 상어는 i번째 상어 ( = shark[i]의 위치는 (r, c))

 

2. 시간 초과 방지를 위해

  상하 이동인 경우에는, s%=(2*R-2)

  좌우 이동인 경우에는, s%=(2*C-2)

을 적용해준 후 나머지 s 만큼만 움직인다!

 

3. 상어가 움직인 후 겹치는 경우, 큰 상어가 작은 상어를 잡아 먹는 것이므로, 

  moved_num 배열을 이용하여 움직인 이후의 상어 정보를 별도로 저장해준다.

 

4. 상어의 위치, 방향 정보가 바뀔 때 잘 저장해준다.

 

C++

#include<iostream>
#include<vector>
#define MAX 101
using namespace std;

struct SHARK {
    bool isdead;
    int r, c, s, d, z; // 위치, 속력, 이동방향, 크기
};

int pc = 0; // 낚시왕의 위치
int ans = 0; // 낚시왕이 잡은 상어 크기의 합

int R, C, M;
int num[MAX][MAX];
int moved_num[MAX][MAX];
vector<SHARK> shark(MAX*MAX);
int dr[] = {-1, 1, 0, 0}; // 상 하 우 좌
int dc[] = {0, 0, 1, -1};

void input(){
    cin >> R >> C >> M;

    int r, c, s, d, z;
    for(int i=1; i<=M; i++){
        cin >> r >> c >> s >> d >> z;
        num[r][c] = i;
        shark[i] = {false, r, c, s, d-1, z};
    }
}

void catch_shark(){

    // 1. 낚시왕이 오른쪽으로 한 칸 이동
    pc++;

    // 2. 땅과 제일 가까운 상어를 잡음
    for(int pr=1; pr<=R; pr++){
        if(num[pr][pc]==0) continue;
        shark[num[pr][pc]].isdead = true; // 상어를 잡음
        ans += shark[num[pr][pc]].z; // ans update
        num[pr][pc] = 0; // 격자판에서 제거
        return;
    }
}

// 3. 상어 이동
void move_shark(){

    int r, c, s, d;
    for(int i=1; i<=M; i++){
        if(shark[i].isdead) continue; // 잡혔거나, 잡아먹힌 상어
        
        r = shark[i].r;
        c = shark[i].c;
        s = shark[i].s;
        d = shark[i].d;
 
        if(d < 2) s%=(2*R-2); // 상하 !!
        else s%=(2*C-2); // 좌우 !!

        while(s--){ // s칸 이동
            r += dr[d];
            c += dc[d];
            if(r<1 || r>R || c<1 || c>C){
                (d==0 || d==2) ? d++ : d--; // 상우, 하좌 (방향 정보 update)
                r += dr[d]*2; c += dc[d]*2;
            }
        }

        // 바뀐 상어 정보 저장
        shark[i].r = r;
        shark[i].c = c;
        shark[i].d = d; // 바뀐 방향 저장 !!

        if(moved_num[r][c] == 0) moved_num[r][c] = i; // 빈 칸인 경우
        else{ // 이미 다른 상어가 있는 경우
            if(shark[i].z > shark[moved_num[r][c]].z){ // 새로 온 상어가 더 큰 경우
                shark[moved_num[r][c]].isdead = true;
                moved_num[r][c] = i;
            }
            else shark[i].isdead = true; // 기존 상어가 더 큰 경우
        }
    }

    // copy and init
    for(int i=1; i<=R; i++){
        for(int j=1; j<=C; j++){
            num[i][j] = moved_num[i][j];
            moved_num[i][j] = 0;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    while(pc < C){
        catch_shark();
        move_shark();
    }
    cout << ans;
}

 

Java

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

public class Main {
	
	static BufferedReader br = null;
	
	static final int[] dr = {-1,1,0,0}; // 상 하 우 좌 
	static final int[] dc = {0,0,1,-1};
	static final int EMPTY = 0;
	
	static class Shark {
		int r, c, s, d, z;
		boolean isDead = false;

		public Shark(int r, int c, int s, int d, int z, boolean isDead) {
			this.r = r;
			this.c = c;
			this.s = s;
			this.d = d;
			this.z = z;
			this.isDead = isDead;
		}
	}
	
	static int R, C, M;
	static Shark[] shark;
	static int[][] num, moved_num;
	
	static void input() throws Exception {
		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());
		num = new int[R][C];
		shark = new Shark[M+1];
		
		for(int i=1; i<=M; i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken()); r--;
			int c = Integer.parseInt(st.nextToken()); c--;
			int s = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken()); d--;
			int z = Integer.parseInt(st.nextToken());
			shark[i] = new Shark(r, c, s, d, z, false);
			num[r][c] = i;
		}
		
		br.close();
	}
	
	static int catch_shark(int col) {
		for(int row=0; row<R; row++) {
			if(num[row][col]!=EMPTY) {
				int n = num[row][col]; // 상어 번호 
				shark[n].isDead = true;
				num[row][col] = EMPTY;
				return shark[n].z; // 잡은 상어 크기 
			}
		} return 0; // 잡을 수 있는 상어가 없는 경우 
	}
	
	static void move_shark() {
		moved_num = new int[R][C]; // 이동 후 정보 저장 
		for(int i=1; i<=M; i++) {
			if(shark[i].isDead) continue; // 이미 잡은 상어인 경우 
			int r = shark[i].r;
			int c = shark[i].c;
			int s = shark[i].s;
			int d = shark[i].d;
			int z = shark[i].z;
			
			if(d<2) s%=(R*2-2); // 상하 이동
			else s%=(C*2-2); // 좌우 이동 	
			
			while(s-->0) { // 남은 만큼 이동 
				r+=dr[d]; c+=dc[d];
				if(r<0 || r>=R || c<0 || c>=C) {
					if(d==0 || d==2) d++; else d--; // 방향 change
					r+=dr[d]*2; c+=dc[d]*2; // 잘못 간 것 까지 돌려 놓음 
				}
			}
			
			// 바뀐 상어 정보 update
			shark[i].r = r;
			shark[i].c = c;
			shark[i].d = d;
			
			if(moved_num[r][c] == EMPTY) moved_num[r][c] = i;
			else { // 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹음 
				int before = moved_num[r][c];
				if(shark[before].z < z) {
					shark[before].isDead = true;
					moved_num[r][c] = i;
				}
				else shark[i].isDead = true;
			}
		}
		
		for(int r=0; r<R; r++) {
			for(int c=0; c<C; c++) num[r][c] = moved_num[r][c];
		}
	}
	
	static void solution() { // 낚시왕이 잡은 상어 크기의 합
		
		int ans = 0;
		for(int col=0; col<C; col++) { // 낚시왕이 오른쪽으로 한 칸 이동
			
			// 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡음 
			ans+=catch_shark(col);
			
			// 상어가 이동
			move_shark();
		}
		System.out.println(ans);
	}

	public static void main(String[] args) throws Exception {
		input();
		solution();
	}
}