[ 삼성 SW역량 평가 17143 ] 낚시왕 (C++)

[ 난이도 ]

★★☆

 

[ 문제 링크 ]

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

 

[ 문제 풀이 ]

문제는 위의 링크를 보고 온다. 이 문제는 간단한 시뮬레이션 문제로 다음과 같은 과정을 거친다

 

첫째, 사람이 이동을 한다.

둘째, 물고기를 잡는다.

셋째, 물고기가 이동한다.

넷째, 겹쳐있는 물고기끼리의 포식이 일어난다.

 

이 조건만 코드로 간단히 구현하면 되는데, 상어가 속도가 최대 1000이다 따라서 for문으로 한 마리씩

1000번을 최대 100 마리씩 돌게 되면 무지하게 많은 연산양이 따르게 된다. 따라서 간단한 요령으로 이문제를

해결해보자. 

그림1

다음과 같은 그림에서 A물고기는 10번을 이동하면 원위치가 된다. B물고기는 6번을 움직이면 제자리로 돌아온다. 뭔가

규칙이 느껴진다. 그렇다. 2*(행의 개수 -1) 2*(열의 개수 -1) 마다 제자리가 반복되므로 A물고기의 입장에서는 10번마다 제자리이므로 11번 움직여야 하는 건 1번 움직이는 것과 같다는 것이다! 이사실만 유의해서 코드를 이해해보자!

 

[ 소스 코드 ]

 

// 헤더 파일을 불러옵니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
// 최대 크기는 100 입니다.
#define Max_Size 101
 
// _Shark의 정보는 각각 좌표,속도,방향,크기 입니다.
struct _Shark
{
    int x;
    int y;
    int speed;
    int direction;
    int size;
};
 
// 맵을 벡터로 받아오고 _Shark 구조체를 포함한 벡터를 만듭니다.
vector<int> Map[Max_Size][Max_Size];
vector<_Shark> Shark;
 
// 각각 위,아래,오른쪽,왼쪽 입니다.
int dx[5] = { 0,-1,1,0, 0 };
int dy[5] = { 0, 0,0,1,-1 };
 
// R : 세로 , C: 가로, M: 상어의 수
int R, C, M;
// r,c,s,d,z : 상어의 정보
int r, c, s, d, z;
 
// 정답 변수
int Answer = 0; 
 
// 입력을 불러옵니다. 맵에는 몇번째 상어인지 넣어줍니다.
void Load_Input()
{
    cin >> R >> C >> M;
    for (int i = 0; i < M; ++i)
    {
        cin >> r >> c >> s >> d >> z;
        Shark.push_back({ r,c,s,d,z,i});
        Map[r][c].push_back(i);
    }
}
 
// 상어를 잡는 함수입니다.
void Get_Shark(int idx)
{
    // 1 ~ R 행 까지 수행합니다.
    for (int i = 1; i <= R; ++i)
    {
        // 맵에 상어가 0마리가 아니라면
        if (Map[i][idx].size() != 0)
        {
            // 해당 상어의 사이즈를 정답에 추가해주고
            Answer = Answer + Shark[Map[i][idx][0]].size;
            
            // 상어의 크기를 0으로 만든 후
            Shark[Map[i][idx][0]].size = 0;
 
            // 맵에서 지워 버립니다.
            Map[i][idx].clear();
            break;
        }
    }
}
 
// 벽을 만났을 때 위쪽을 보고있으면 아래쪽을 향하도록
// 오른쪽을 보고 있으면 왼쪽을 향하도록 하는 함수.
int Change_Direction(int d)
{
    if (d == 1) return 2;
    if (d == 2) return 1;
    if (d == 3) return 4;
    if (d == 4) return 3;
}
 
// 상어가 움직이게 하는 함수입니다.
void Move_Shark()
{
    // 맵을 모두 비워줍니다.
    for (int i = 0; i < Shark.size(); i++)
    {
        if (Shark.at(i).size == 0) continue;
        int x = Shark.at(i).x;
        int y = Shark.at(i).y;
        Map[x][y].clear();
    }
    // 상어의 수만큼 반복합니다.
    for (int i = 0; i < Shark.size(); ++i)
    {    
        // 죽거나 잡힌 상어라면 넘어갑니다.
        if (Shark.at(i).size == 0) continue;
 
        // 상어의 정보를 가져옵니다.
        int x = Shark.at(i).x;
        int y = Shark.at(i).y;
        int d = Shark.at(i).direction;
        int v = Shark.at(i).speed;
 
        // 2*(R-1), 2*(C-1)회 마다 제자리이므로 나머지를 가져옵니다.
        if (d == 1 || d == 2) v = v % (2 * (R - 1));
        if (d == 3 || d == 4) v = v % (2 * (C - 1));
 
        
        int nx = x;
        int ny = y;
 
        for (int j = 0; j < v; ++j)
        {    
            // 이동합니다.
            nx = nx + dx[d];
            ny = ny + dy[d];
            // 벽을 만난다면
            if (nx <1 || nx > R || ny <1 || ny >C)
            {    //방향을 바꿔주고
                d = Change_Direction(d);
 
                // 2칸 움직입니다. (맵을 벗어났기 때문에 2칸을 이동합니다)
                nx = nx + 2 * dx[d];
                ny = ny + 2 * dy[d];
            }
        }
        // 새로운 상어의 정보를 입력하고
        Shark.at(i).x = nx;
        Shark.at(i).y = ny;
        Shark.at(i).direction = d;
 
        // 지도에 추가해줍니다.
        Map[nx][ny].push_back(i);
 
    }
}
 
// Sort의 사용자 지정함수 입니다.
bool Standard(int A, int B)
{
    if (Shark[A].size > Shark[B].size) return true;
    return false;
}
 
// 상어끼리 잡아먹는 함수입니다.
void Survive_Shark()
{
    // 모든 칸을 탐색합니다.
    for (int i = 1; i <= R; ++i)
    {
        for (int j = 1; j <= C; ++j)
        {
            // 만약 상어가 2마리 이상 있다면
            if (Map[i][j].size() > 1)
            {
                // Standard 기준처럼 사이즈가 큰 순서대로 나열합니다.
                sort(Map[i][j].begin(), Map[i][j].end(),Standard);
 
                // 따라서 0 번째 상어가 살아있는 상어가 됩니다.
                int Live_Shark = Map[i][j][0];
 
                // 1번째 상어 부터는 다 죽여줍니다.
                for (int k = 1; k < Map[i][j].size(); ++k)
                {
                    Shark[Map[i][j][k]].size = 0;
                }
                // 맵을 정리하고 살아있는 상어만 넣어줍니다.
                Map[i][j].clear();
                Map[i][j].push_back(Live_Shark);
            }
        }
    }
}
 
// 상어가 더이상 없다면 멈추고 정답을 반환합니다.
bool Check()
{
    for (int i = 0; i < Shark.size(); i++)
    {
        if (Shark[i].size != 0) return false;
    }
    return true;
}
 
// 해결함수.
void Solve()
{
    Load_Input();
    if (M == 0)
    {
        cout << 0 << endl;
        return 0;
    }
 
    for (int i = 1; i <= C; ++i)
    {
        if (Check() == true) break;
        Get_Shark(i);
        Move_Shark();
        Survive_Shark();
    }
 
    cout << Answer;
}
 
int main()
{
    Solve();
 
    return 0;
}