[Algorithm] Baekjoon 16236번 : 아기상어

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

16236번: 아기 상어

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
 
using namespace std;
 
 
struct Node
{
    int y;
    int x;
    int second;
};
 
vector<vector<int>> m(21, vector<int>(21));
int sharkSize = 2;
int dir[4][2] = { {-1,0},{0,-1}, {0,1}, {1,0} };
int n = 0;
 
bool cmp(const Node& a, const Node& b)
{
    if (a.y == b.y)
    {
        return a.x < b.x;
    }
 
    return a.y < b.y;
}
 
Node FindClosestFish(int sy, int sx)
{
    queue<Node> q;
    q.push({ sy,sx,0 });
 
    vector<vector<int>> tempMap = m;
    vector<Node> results;
    tempMap[sy][sx] = -1;
    bool isFirstCheck = false;
    int minSecond = 0;
 
    while (!q.empty())
    {
        Node curNode = q.front();
        q.pop();
 
        int curY = curNode.y;
        int curX = curNode.x;
        int curSecond = curNode.second;
 
        if (m[curY][curX] >= 1 && m[curY][curX] < sharkSize) // 먹잇감 발견하면
        {
            if (!isFirstCheck) // 첫먹이 발견시
            {
                isFirstCheck = true;
                minSecond = curSecond; // 기준시간
                results.push_back({ curY,curX,curSecond });
            }
            else // 두번째부터 먹이발견시
            {
                if (curSecond == minSecond)
                {
                    results.push_back({ curY,curX,curSecond });
                }
                else
                {
                    break;
                }
            }
        }
 
        for (int i = 0; i < 4; i++)
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY >= n) continue;
            if (nextX < 0 || nextX >= n) continue;
            if (tempMap[nextY][nextX] > sharkSize) continue; // 해당칸의 물고기가 상어보다 더 크면
            if (tempMap[nextY][nextX] == -1) continue; // 물고기가 있는곳은 아니고, 이미 지났던 일반통로 (0이였던 곳)
 
            // 먹을수 있는 물고기거나, 똑같은 크기물고기거나, 그냥 0
            q.push({ nextY,nextX,curSecond + 1 });
            tempMap[nextY][nextX] = -1;
        }
    }
 
    if (results.size() != 0)
    {
        sort(results.begin(), results.end(), cmp);
        return results[0];
    }
    else
        return { -100,-100,-100 };
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int sy = 0;
    int sx = 0;
    int second = 0;
    int sizeCount = 0;
 
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> m[i][j];
 
            if (m[i][j] == 9)
            {
                sy = i;
                sx = j;
            }
        }
    }
 
    while (1)
    {
        m[sy][sx] = 0;
        Node closestFish = FindClosestFish(sy, sx);
 
        if (closestFish.y == -100) // 먹을 수 있는 물고기가 더이상없으면.
        {
            break;
        }
 
        second += closestFish.second;
        sy = closestFish.y;
        sx = closestFish.x;
 
        sizeCount++;
 
        if (sizeCount == sharkSize)
        {
            sharkSize++;
            sizeCount = 0;
        }
    }
 
    cout << second;
 
    return 0;
}
 
 

 

 

 

접근은 잘 했는데 방문체크에서 헷갈려서 좀 걸렸던 문제.

BFS돌려서 가장 먼저 조건에 맞는 노드가 걸렸을 때의 시간을 기준으로 체크한 후, results에 넣어놓고 더 탐색한다.

BFS특성상, 먼저 발견한게 가장 가까운 물고기인건 보장되어진다. 

 

다만, 거리값이 같은 물고기가 여러마리일 수 있다는것을 잊으면 안된다.

그래서 일단 처음 먹을수 있는 물고기를 만나면 그때의 시간을 절대기준으로 세워놓고, 이후 조건에 맞는 물고기를 찾았을 때 해당 절대기준이랑 같으면 마찬가지로 results에 넣어주고, 절대기준시간에 안맞으면 이제 더이상 절대기준시간에 일치하는 물고기는 존재하지 않기때문에 바로 반복문을 탈출해도된다.

절대 첫물고기 찾았다고 바로 탈출하면 안된다. 조건에 맞는 물고기는 여러마리일 수 있다.

 

그러면 results에는 가장 가까운 물고기들(거리값이 같은 물고기들)이 반드시 들어있다고 보장이 되어지는데, 2마리 이상일 경우 가장 위쪽에 있는 물고기이거나, 같은 y값이면 왼쪽에 있는 물고기가 우선순위이니 해당 조건에 맞게 cmp함수를 작성하고 sort시켜준다.

 

위 코드같은 경우 FindClosestFish()를 수행할 때마다 원본을 복사한 맵을 사용했다.

더 이상의 탐색을 막기위한 방문체크(-1)은 tempMap(복사한맵)에다가 체크하고, 꺼낸 노드가 조건에 맞는 노드인지 체크하는것은 원본맵으로 했다. 

원본맵 하나로 하려니까 헷갈리기도 하고, 결국 다음 체크를 위해서는 어차피 방문체크했던 -1들을 다시 원래대로 돌려놔야한다. 복사비용이 얼마나 되는지는 모르겠지만, 수행속도는 0ms로 잘 나온것같다.