17143번: 낚시왕 (백준 온라인 저지, C++)

문제 풀이

 

알고리즘은 다음과 같습니다. 우선 두 개의 큰 함수를 만들었습니다.

- fishing: 물고기 잡는 함수

- moving: 물고기가 이동하는 함수

 

물고기를 잡는 함수 같은 경우 해당 열에서 맨 위에 위치하는 물고기를 삭제해주면 되는 간단한 함수입니다. 그러나 물고기가 이동하는 함수같은 경우는 약간 까다롭습니다.

우선 물고기가 들어있는 arr과 같은 _tmp 배열을 만들어주고 arr을 비워줍니다. _tmp 배열을 탐색하면서 물고기가 있다면 moveThisShark 함수를 이용하여 이동시켜 주었습니다. moveThisShark 함수에서는 물고기가 이동했을 경우 어디로 이동하는지에 대한 좌표를 리턴해 주었습니다.

이 때, 속력이 매우 큰 경우를 고려하여 한번 왔다갔다 하고 제자리로 돌아온 경우를 배제하기 위해, 다음과 같은 식을 적용해 주었습니다.

이 후, 반환된 좌표값의 arr을 참조하였을 때, 이미 물고기가 있다면 이는 이동을 마친 물고기가 있는 것으로 따라서 물고기의 크기를 비교하여 더 큰 물고기를 배열에 넣어주었습니다. 물고기가 없다면 바로 배열에 넣어줍니다. 중복을 방지하기 위해 이동을 마친다면 _tmp의 값을 삭제하여 줍니다. 자세한 풀이는 코드를 첨부하도록 하겠습니다.

 

 

코드

 

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
 
using namespace std;
 
struct shark {
    int s; //속력
    int d; //이동 방향
    int z; //크기
};
 
int R, C, M;
shark arr[101][101];
shark _tmp[101][101];
int dr[] = { -1, 1, 0, 0 };
int dc[] = { 0, 0, 1, -1 };
 
void _reset(string s, int r, int c) {
    if (s == "arr") {
        arr[r][c].s = 0; arr[r][c].d = 0; arr[r][c].z = 0;
    }
    else {
        _tmp[r][c].s = 0; _tmp[r][c].d = 0; _tmp[r][c].z = 0;
    }
}
 
void _set(string s, int r, int c, int ss, int dd, int zz) {
    if (s == "arr") {
        arr[r][c].s = ss; arr[r][c].d = dd; arr[r][c].z = zz;
    }
    else {
        _tmp[r][c].s = ss; _tmp[r][c].d = dd; _tmp[r][c].z = zz;
    }
}
 
int fishing(int a) {
 
    for (int i = 1; i <= R; i++) {
        if (arr[i][a].z > 0) {
            int tmp = arr[i][a].z;
            _reset("arr", i, a);
            return tmp;
        }
    }
    return 0;
}
 
pair<int,int> moveThisShark(int r, int c) {
    
    int tmp_r = r;
    int tmp_c = c;
 
    shark sh;
    sh.s = _tmp[r][c].s; sh.d = _tmp[r][c].d; sh.z = _tmp[r][c].z;
 
    if (sh.d == 0 || sh.d == 1) sh.s -= (sh.s / (R * 2 - 2)) * (R * 2 - 2);
    else sh.s -= (sh.s / (C * 2 - 2)) *(C * 2 - 2);
 
    for (int i = 0; i < sh.s; i++) {
        int nr = r + dr[sh.d];
        int nc = c + dc[sh.d];
        if (nr < 1 || nr > R || nc < 1 || nc > C) {
            if (sh.d == 0) sh.d = 1;
            else if (sh.d == 1) sh.d = 0;
            else if (sh.d == 2) sh.d = 3;
            else sh.d = 2;
            r += dr[sh.d];
            c += dc[sh.d];
        }
        else {
            r = nr;
            c = nc;
        }
    }
 
    _tmp[tmp_r][tmp_c].d = sh.d;
 
    return make_pair(r, c);
}
 
void moving() {
 
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            if (arr[i][j].z > 0) {
                _set("_tmp", i, j, arr[i][j].s, arr[i][j].d, arr[i][j].z);
                _reset("arr", i, j);
            }
        }
    }
 
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            if (_tmp[i][j].z > 0) {
 
                pair<int, int> x;
                x = moveThisShark(i, j);
 
                if (arr[x.first][x.second].z > 0) {
                    if (arr[x.first][x.second].z < _tmp[i][j].z) {
                        _set("arr", x.first, x.second, _tmp[i][j].s, _tmp[i][j].d, _tmp[i][j].z);
                    }
                }
                else {
                    _set("arr", x.first, x.second, _tmp[i][j].s, _tmp[i][j].d, _tmp[i][j].z);
                }
                _reset("_tmp", i, j);
            }
        }
    }
}
 
int main() {
 
    int ans = 0;
    cin >> R >> C >> M;
 
    for (int i = 0; i < M; i++) {
        int r, c;
        cin >> r >> c;
        cin >> arr[r][c].s >> arr[r][c].d >> arr[r][c].z;
        arr[r][c].d -= 1;    
    }
 
    for (int i = 1; i <= C; i++) {
        ans += fishing(i);
        moving();
        ans += 0;
    }
 
    cout << ans;
 
    return 0;
}

 

 

제출 결과

 

 

 

문제 출처

 

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

17143번: 낚시왕