개요

오랫동안 코딩을 쉬었다.
그러고 최근, 아는 선배와 함께 웹 개발을 다시 시작하는데, 코딩을 너무 오래 쉬었던 탓일까, 코드를 짜는 것이 예전에 비해 확실히 미숙해졌다는 생각이 들었다.
그러던 중 함께 웹 개발을 하던 선배가 구현 알고리즘을 추천해 줬고, 코딩은 안해도 PS는 종종 했기에 선배가 구현 알고리즘과 함께 추천해준 문제를 백준의 17143번(낚시왕) 풀어보기로 했다.

문제링크

문제 풀이

문제를 본격적으로 풀기에 앞서 문제에 등장하는 인간과 상어, 두 객체에 대한 행동 및 특징을 정리해 보자.

상어

객체가 가지는 요소 : 위치(행,열), 속도(칸/초), 무게, 방향
동작
	(1) 어떠한 시간 t에 대해서 낚시왕이 낚시를 끝낸 직후 상어들은 자신이 정해진 속도에 따라 
    움직이며, 모든 상어의 움직임이 끝나면 t+1의 시간으로 변한다.
	(2) 상어는 벽을 만나면 그 자리에서 방향을 반대로 바꿔 속력을 유지한채 이동한다.
    (3) 모든 이동이 끝난 후 한 칸에 두 마리 이상의 상어가 있다면, 가장 무거운 상어가 나머지 
    상어를 모두 잡아먹는다.

낚시왕

객체가 가지는 요소 : 위치(열), 잡은 상어의 무게 합
동작
	(1) 매 초가 시작될 때, 낚시왕은 다음 열로 이동함
    (2) 이동한 직후, 해당 열에 있는 상어 중 가장 작은 행 index에 있는 상어를 잡는다.
    (3) 마지막 열에 도착하여 동작 (2)를 끝내고 나면 낚시왕은 동작을 멈춘다.

대충 이렇게 정리를 하고 보니, 여러 마리가 존재하고, 행동이 상대적으로 복잡한 상어와 달리, 혼자만 존재하는 낚시왕에 대해서는 굳이 별도 객체를 구현할 필요가 없어 보인다.

이렇게 정리를 끝냈으니, 우선 문제에 필요한 변수부터 정리해보자.

int M;
int total_size = 0;
list<shark> shark_list; //상어 객체 list
list<shark> dummy_list;
vector<vector<list<shark>::iterator>> grid; // 상어의 위치 탐색을 위한 2차원 vector
list<shark>::iterator empty_flag = dummy_list.end(); // 빈공간 표시

위의 변수 선언부에서 눈여겨 봐야할 부분은 empty_flag 부분이다.
grid 벡터에서 빈 공간을 표시하기 위해 아무생각없이 nullptr과 같은 것들로 처리하려고 했으나, iterator에는 NULL 같은거 없기에 아무것도 없는 dummy_list의 end iterator를 빈공간을 표시하는 empty_flag로 사용했다.

그리고 객체 저장용으로 list를 사용한 이유는, 해당 원소의 위치는 grid에 저장되어 있는데, 상어가 잡아먹히거나 낚시왕에게 잡힐 경우 grid와 container에서 삭제되어야 했다. 이때, 삭제 후에도 grid에서 container로 고유하게 접근할 수 있도록 해야했고, 삭제 후에도 모든 원소의 iterator가 고유하게 남아있는 container 중 list를 선택하게 되었다.

상어에 대한 객체 (shark) 코드

class shark {
private:
    int size;
    int speed;
    int dir_ind;
    int row;
    int col;
public:
    shark() {}
    
    shark(int _row, int _col, int _speed, int _dir_ind, int _size) 
    : row(_row), col(_col), speed(_speed), dir_ind( _dir_ind), size(_size){}
    
    ~shark() {}
    
    int getSize(void) {return size;}
    
    pair<int,int> getLocation(void) {return make_pair(row, col);}
    
    void move(list<shark>::iterator &it,
    		  list<shark> &shark_list,
              vector<vector<list<shark>::iterator>> &grid,
              const list<shark>::iterator &empty_flag) {
        for(int remain_move = speed % (2 * ((Dir[dir_ind][0] != 0 ? R : C) - 1)); remain_move > 0; --remain_move)
        {
            int next_row = row + Dir[dir_ind][0];
            int next_col = col + Dir[dir_ind][1];
            
            if(next_row == R || next_row == -1 
            || next_col == C || next_col == -1)
                dir_ind = !(dir_ind - (dir_ind > 1 ? 2 : 0)) 
                		  + (dir_ind > 1 ? 2 : 0);
            
            row += Dir[dir_ind][0];
            col += Dir[dir_ind][1];
        }
        
        pair<int,int> cur_loc = getLocation();
        
        if(grid[cur_loc.first][cur_loc.second] == empty_flag 
        || it->getSize() > grid[cur_loc.first][cur_loc.second]->getSize())
        {
            if(grid[cur_loc.first][cur_loc.second] != empty_flag)
                shark_list.erase(grid[cur_loc.first][cur_loc.second]);
            grid[cur_loc.first][cur_loc.second] = it;
            it++;
        }
        else
            it = shark_list.erase(it);
    }
};

main 코드를 깔끔하게 만들고 싶은 욕심에 객체 멤버함수가 많이 지저분하다.
(객체와 main함수 중 무엇을 미니멀하게 해야할지 결정하는건 여전히 어렵다.)

shark 객체의 멤버함수에서 가장 중요한건 move 함수이다.
상어가 움직인 후 만약 자신이 도착한 위치에 다른 상어가 먼저 도착해있다면,
그 상어를 잡아 먹을건지, 아니면 잡아 먹힐건지 선택해야한다.
이를 위해 앞서 말한 grid의 값과 대조하여 위의 동작을 수행할 수 있게 된다.

동작 코드

for(int time = 0; time < C; time++)
    {
        int row = 0;
        while(row < R && grid[row][time] == empty_flag) row++;
        
        if(row < R)
        {
            list<shark>::iterator it = grid[row][time];
            grid[row][time] = empty_flag;
            total_size += it->getSize();
            shark_list.erase(it);
        }
        
        pair<int,int> cur_loc;
        for(list<shark>::iterator it = shark_list.begin(); it != shark_list.end(); it++)
        {
            cur_loc = it->getLocation();
            grid[cur_loc.first][cur_loc.second] = empty_flag;
        }
        
        for(list<shark>::iterator it = shark_list.begin(); it != shark_list.end(); )
        {
            it->move(it, shark_list, grid, empty_flag);
        }
    }

낚시꾼의 열(col) 위치 index는 시간(time) index와 같기에 편의상 동일시 하여 코드를 작성했다.
매 시간마다 낚시꾼은 해당 열에서 가장 작은 행 index에 있는 상어를 찾아서 잡고, 모든 상어가 움직이기 전 전처리 작업으로 grid에 있는 상어들의 iterator를 모두 지워 다음번 상어의 move에서는 해당 시간의 동작만 반영할 수 있도록 했다. (동작이 종료한 후 같은 칸에 있는 상어 중 가장 큰 상어가 나머지 상어를 모두 잡아먹는다 했으니.)

전체코드

//MEMORY USAGE : 2684KB , TIME REQUIRED : 116ms
#include <iostream>
#include <vector>
#include <list>
using namespace std;

const int Dir[4][2] = {{-1,0}, {1,0}, {0,1}, {0,-1}};

int R, C;

class shark {
private:
    int size;
    int speed;
    int dir_ind;
    int row;
    int col;
public:
    shark() {}
    
    shark(int _row, int _col, int _speed, int _dir_ind, int _size) : row(_row), col(_col), speed(_speed), dir_ind( _dir_ind), size(_size){}
    
    ~shark() {}
    
    int getSize(void) {return size;}
    
    pair<int,int> getLocation(void) {return make_pair(row, col);}
    
    void move(list<shark>::iterator &it,list<shark> &shark_list,
              vector<vector<list<shark>::iterator>> &grid, const list<shark>::iterator &empty_flag) {
        for(int remain_move = speed % (2 * ((Dir[dir_ind][0] != 0 ? R : C) - 1)); remain_move > 0; --remain_move)
        {
            int next_row = row + Dir[dir_ind][0];
            int next_col = col + Dir[dir_ind][1];
            
            if(next_row == R || next_row == -1 || next_col == C || next_col == -1)
                dir_ind = !(dir_ind - (dir_ind > 1 ? 2 : 0)) + (dir_ind > 1 ? 2 : 0);
            
            row += Dir[dir_ind][0];
            col += Dir[dir_ind][1];
        }
        
        pair<int,int> cur_loc = getLocation();
        
        if(grid[cur_loc.first][cur_loc.second] == empty_flag || it->getSize() > grid[cur_loc.first][cur_loc.second]->getSize())
        {
            if(grid[cur_loc.first][cur_loc.second] != empty_flag)
                shark_list.erase(grid[cur_loc.first][cur_loc.second]);
            grid[cur_loc.first][cur_loc.second] = it;
            it++;
        }
        else
            it = shark_list.erase(it);
    }
};


int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int M;
    int total_size = 0;
    list<shark> shark_list;
    list<shark> dummy_list;
    vector<vector<list<shark>::iterator>> grid;
    list<shark>::iterator empty_flag = dummy_list.end();
    
    cin>>R>>C>>M;
    grid.assign(R, vector<list<shark>::iterator>(C, empty_flag));
    
    for(int i=0; i<M; ++i)
    {
        int r, c, s, d, z;
        cin>>r>>c>>s>>d>>z;
        
        r--; c--;
        shark_list.push_back(shark(r,c,s,d-1,z));
        grid[r][c] = next(shark_list.end(), -1);
    }
    
    for(int time = 0; time < C; time++)
    {
        int row = 0;
        while(row < R && grid[row][time] == empty_flag) row++;
        
        if(row < R)
        {
            list<shark>::iterator it = grid[row][time];
            grid[row][time] = empty_flag;
            total_size += it->getSize();
            shark_list.erase(it);
        }
        
        pair<int,int> cur_loc;
        for(list<shark>::iterator it = shark_list.begin(); it != shark_list.end(); it++)
        {
            cur_loc = it->getLocation();
            grid[cur_loc.first][cur_loc.second] = empty_flag;
        }
        
        for(list<shark>::iterator it = shark_list.begin(); it != shark_list.end(); )
        {
            it->move(it, shark_list, grid, empty_flag);
        }
    }
    
    cout<<total_size;
    
    return 0;
}

여담

확실히 이런 구현 문제가 코딩 감 익히기엔 좋은 것 같다.
iterator에 대해 오락가락 했던 개념도 다시한번 보고, PS 치곤 긴 코드의 오류가 나지 않도록 여러 요소를 따져가는 과정들이 다시금 나에게 코딩의 즐거움을 상기시켜줬다.