[BOJ] 17143. 낚시왕

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

17143번: 낚시왕

(수정)

이전의 풀이가 재채점 후에 시간 초과로 바뀌어서 다시 풀었다...

속력 s만큼 이동하면 안되고 결국 똑같은 범위 안에서 왔다 갔다 하는 것이므로 % 연산을 사용하여 이동을 단축시킬 수 있다. 즉 상하로 움직이는 경우에는 (r-1) * 2 , 좌우로 움직이는 경우에는 (c-1) * 2  만큼 움직일 때 원래 자리로 돌아온다.

 

//상하로 움직이는 경우

  if (d <= 2) {

        s = s % ((R-1) * 2);

  }

  else { //좌우로 움직이는 경우

        s = s % ((C-1) * 2);

  }

 

s만큼 이동하기 전에 이렇게 추가해줘서 pass하였다.

 

 

 

 

시뮬레이션 문제인데 상어들이 같은 곳에 있을 때의 처리를 해주는 게 어려웠다.

swea의 미생물 격리(?) 문제랑 살짝 비슷한 것 같다(미생물 격리가 더 어려움)

 

문제에서 주어지는 상어의 좌표, 속력, 방향, 크기의 정보와 추가적으로 살아있는지 여부를 확인할 bool변수를

구조체로 저장하여 관리하였다.

또한, 배열을 만들어서 상어의 위치에 상어의 인덱스를 저장하였다.(상어의 인덱스는 입력받은 순서다)

예를 들어 두 번째 상어의 좌표가 (1,3)이었다면 map [1][3] = 2

이런 식으로 저장하고 이동하거나 죽으면 다시 0으로 바꿔줬다.

 

이 배열을 활용하면 낚시왕이 상어를 잡을 때 낚시왕이 서있는 열만 배열에서 쭉 확인해주면 되므로

쉽게 구현할 수 있다.

 

두 마리 이상의 상어들이 같은 곳에 위치할 때에도 이 배열을 확인하였다.

이동할 좌표에 대해 다음과 같이 나눠서 처리해주었다.

r, c로 이동한다고 가정했을 때,

• map[r][c] = 0 인 경우 ( 다른 상어가 없다)
  • 바로 map[r][c]에 현재 상어의 인덱스를 저장하면 된다.
• map[r][c] > i 인 경우 ( 이전 인덱스의 상어가 와 있는 경우 ) // 인덱스 순서대로 진행하지면 동시에 일어나는 일이다!!
  • 현재 이동(같은 시간)에서 와 있는 상어이므로 크기를 비교 후 더 큰 상어가 해당 위치에 남아있게 된다.
• map[r][c] < i 인 경우 ( 다음 인덱스의 상어의 번호가 있는 경우) 이전 이동(이전 시간)에서의 상어의 위치이다.
  • 다음 인덱스의 상어는 어차피 좀 이따 이동시켜줄 것이므로 그냥 첫 번째 경우처럼 바로 저장해주면 된다.

 

좀 더 자세한 설명은 코드의 주석 참고!

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int R, C, M;
int dx[] = { 0,-1,1,0,0 };
int dy[] = { 0,0,0,1,-1 };
 
int map[101][101];
 
 
struct Shark {
    int r;
    int c;
    int s;
    int d;
    int z;
 
    //살아있는지 여부
    bool isAlive;
};
 
vector<Shark> vt;
 
int getShark(int c) {
    int getsize = 0;
 
    //낚시왕이 서있는 열의 행들만 검사한다.
    for (int i = 1; i <= R; i++) {
 
        //상어가 있으면
        if (map[i][c] != 0) {
 
            //크기를 받아오고
            getsize = vt[map[i][c]].z;
 
            //잡았으므로 죽인다.
            vt[map[i][c]].isAlive = false;
 
            //해당위치에서 지워준다.
            map[i][c] = 0;
 
            //가장 가까운 한마리만 잡음로 break
            break;
        }
    }
 
    //크기를 리턴
    return getsize;
}
 
void sharkMove() {
 
    int r, c, s, d, z;
    for (int i = 1; i <= M; i++) {
        //죽은 상어는 skip
        if (vt[i].isAlive == false) continue;
 
        r = vt[i].r;
        c = vt[i].c;
        s = vt[i].s;
        d = vt[i].d;
        z = vt[i].z;
 
        //다른 곳으로 이동할 것이므로 원래 있던 자리를 0으로 넣어준다.
        //이전 index의 상어가 현재 상어의 자리에 와 있지 않은 경우에만 0으로 초기화
        if (map[r][c] == i) {
            map[r][c] = 0;
        }
 
        
        //s를 줄여준다.
        if (d <= 2) {
            s = s % ((R-1) * 2);
        }
        else {
            s = s % ((C-1) * 2);
        }
        
 
        //스피드(s)만큼 d방향으로 이동
        for (int j = 0; j < s; j++) {
            r += dx[d];
            c += dy[d];
 
            //범위를 넘어가는 경우
            if (r < 1 || c < 1 || r > R || c > C) {
                if (d == 1 || d == 3) {
                    d += 1;
                }
                else {
                    d -= 1;
                }
 
                //범위 안으로 하나 들어오고
                r += dx[d];
                c += dy[d];
 
                //j는 다시 빼준다.(한 번 잘못 움직인 것 이므로)
                j--;
            }
 
        }
 
        //변경된 좌표와 방향을 상어 정보에 새로 저장
        vt[i].r = r;
        vt[i].c = c;
        vt[i].d = d;
 
 
        //이동한 곳에 다른 상어가 없다면 바로 저장
        if (map[r][c] == 0) {
            map[r][c] = i;
        }
        else if (map[r][c] < i) {
            // 이전 인덱스의 상어가 있는 경우에는 크기가 더 큰 상어가 더 작은 상어를 잡아먹는다.
 
            int tmp = vt[map[r][c]].z;
            if (z > tmp) {
                //현재 인덱스의 상어가 더 큰 경우 원래 있던 상어를 잡아먹는다.
                vt[map[r][c]].isAlive = false;
                map[r][c] = i;
            }
            else {
                //현재 인덱스의 상어가 더 작은 경우 잡아먹힌다.
                vt[i].isAlive = false;
            }
        }
        else {
            //현재 인덱스보다 뒷순서의 상어라면 어차피 이동할 것이므로 그냥 덮어쓴다.
            map[r][c] = i;
        }
 
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> R >> C >> M;
 
 
    //상어의 수가 0인 경우는 바로 0을 출력하고 종료
    if (M == 0) {
        cout << 0 << '\n';
        return 0;
    }
 
    int r, c, s, d, z;
 
    //index를 1부터 시작해주기 위해서 0번째에 아무거나 넣어놓는다.
    vt.push_back({ 0,0,0,0,0 });
    for (int i = 1; i <= M; i++) {
        cin >> r >> c >> s >> d >> z;
 
        //상어 정보를 벡터에 넣는다.
        vt.push_back({ r,c,s,d,z,true });
 
        //배열에 위치한 상어의 index를 저장
        map[r][c] = i;
    }
 
    int ans = 0;
    //C만큼 실행
    for (int i = 1; i <= C; i++) {
        ans += getShark(i);
        sharkMove();
    }
 
    cout << ans << "\n";
 
    return 0;
}