[BFS 알고리즘] 아기 상어 ★★☆

기출 : 2020 삼성전자 공채

 

단순한 아이디어지만 항상 구현할때 쌍욕이 나오는 전형적인 삼성전자 문제다

 

아이디어는 다음과 같다

 

1. 가장 가까운 물고기 찾기

2. 물고기를 찾아 이동하기

3. 물고기가 없다면 답 출력, 있다면 1번으로 이동

 

각 단계별로 생각해 보자

 

1. 가장 가까운 물고기 찾기

 

현재 위치에서부터 BFS를 시작해 제일 처음 물고기를 발견하면 그 거리에 해당하는 물고기들을 따로 저장한다

 

우리가 원하는 것은 X좌표가 가장 작고, 같다면 Y좌표가 가장 작은 물고기이다

 

저장된 물고기들을 STL Sort 함수를 이용해 위 기준에 맞게 정렬해준다

bool cmp(pair<int,int> a, pair<int,int> b) {
    if (a.X < b.X) return true;
    else if (a.X > b.X)return false;
    else {
        if (a.Y<= b.Y) return true;
        else if (a.Y > b.Y)return false;
    }
}

첫 번째 원소가 바로 원하는 물고기이고 이를 함수로 작성하면 다음과 같다

pair<int, int> findNext() {
    queue<node> q;
    bool visited[21][21];
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            visited[i][j] = false;
        }
    }
    visited[cur.X][cur.Y] = true;
    node first(cur, 0);
    q.push(first);
    int mindist = 0x7f7f7f7f;
    vector<pair<int, int>> nearest;
    while (!q.empty()) {
        node now = q.front(); q.pop();
        if (now.dist == mindist) break;
        for(int i=0;i<4;i++){
            int mx = now.coor.X + dx[i];
            int my = now.coor.Y + dy[i];
            if (mx < 0 || my < 0 || mx >= n || my >= n) continue;
            if (visited[mx][my]) continue;
            if (board[mx][my] > board[cur.X][cur.Y]) continue;
            if (board[mx][my] !=0 && board[mx][my] < board[cur.X][cur.Y]) {
                nearest.push_back({ mx,my });
                mindist = now.dist + 1;
                visited[mx][my] = true;
            }
            else if (board[mx][my] == 0 || board[mx][my] == board[cur.X][cur.Y]) {
                node tmp({ mx,my }, now.dist + 1);
                q.push(tmp);
                visited[mx][my] = true;
            }
        }
    }
    if (!nearest.empty()) {
        sort(nearest.begin(), nearest.end(), cmp);
        return nearest[0];
    }
    else return {-1,-1};
}

2. 물고기를 찾아 이동하기

 

아기 상어가 찾은 물고기를 먹는 과정이다

 

물고기를 찾는 것이 아니라 실제로 이동하는 과정이기 때문에 거리에 따라 탐색 시간을 증가시켜줘야 한다

 

BFS를 통해 물고기를 찾은 뒤 board를 갱신해준다

void moveTo(pair<int,int> next) {
    queue<node> q;
    node nod(cur, 0);
    bool visited[21][21];
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            visited[i][j] = false;
        }
    }
    q.push(nod);
    while (!q.empty()) {
        node now = q.front(); q.pop();
        for (int i = 0;i < 4;i++) {
            int mx = now.coor.X + dx[i];
            int my = now.coor.Y + dy[i];
            if (mx < 0 || my < 0 || mx >= n || my >= n) continue;
            if (visited[mx][my]) continue;
            if (board[mx][my] > board[cur.X][cur.Y]) continue;
            if (mx == next.X && my == next.Y) {
                cnt++;
                if (cnt == siz) {
                    cnt = 0;
                    siz++;
                }
                ans += (now.dist + 1);
                board[cur.X][cur.Y] = 0;
                cur = { mx,my };
                for (int i = 0;i < fish.size();i++) {
                    if (fish[i].X == mx && fish[i].Y == my) {
                        fish.erase(fish.begin() + i);
                        break;
                    }
                }
                board[mx][my] = siz;
                return;
            }
            else {
                visited[mx][my] = true;
                node nxt({ mx,my }, now.dist + 1);
                q.push(nxt);
            }
        }
    }
}

3. 물고기가 없다면 답 출력, 있다면 1번으로 이동

 

이 과정은 main 함수에서 고려해야 할 부분이다

 

코드는 다음과 같다

    while (!fish.empty()) {
        pair<int, int> nxt = findNext();
        if (nxt.X != -1) moveTo(findNext());
        else { cout << ans; return 0; }
    }
    cout << ans;

 

 

각 함수를 합친 전체 코드는 다음과 같다

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int n;
int board[21][21];
int siz = 2;
int cnt;
int ans;
vector<pair<int, int>> fish;
pair<int, int> cur;
struct node {
    pair<int, int> coor;
    int dist=0;
    node(pair<int,int> c, int d) : coor(c), dist(d) {};
};

bool cmp(pair<int,int> a, pair<int,int> b) {
    if (a.X < b.X) return true;
    else if (a.X > b.X)return false;
    else {
        if (a.Y<= b.Y) return true;
        else if (a.Y > b.Y)return false;
    }
}

pair<int, int> findNext() {
    queue<node> q;
    bool visited[21][21];
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            visited[i][j] = false;
        }
    }
    visited[cur.X][cur.Y] = true;
    node first(cur, 0);
    q.push(first);
    int mindist = 0x7f7f7f7f;
    vector<pair<int, int>> nearest;
    while (!q.empty()) {
        node now = q.front(); q.pop();
        if (now.dist == mindist) break;
        for(int i=0;i<4;i++){
            int mx = now.coor.X + dx[i];
            int my = now.coor.Y + dy[i];
            if (mx < 0 || my < 0 || mx >= n || my >= n) continue;
            if (visited[mx][my]) continue;
            if (board[mx][my] > board[cur.X][cur.Y]) continue;
            if (board[mx][my] !=0 && board[mx][my] < board[cur.X][cur.Y]) {
                nearest.push_back({ mx,my });
                mindist = now.dist + 1;
                visited[mx][my] = true;
            }
            else if (board[mx][my] == 0 || board[mx][my] == board[cur.X][cur.Y]) {
                node tmp({ mx,my }, now.dist + 1);
                q.push(tmp);
                visited[mx][my] = true;
            }
        }
    }
    if (!nearest.empty()) {
        sort(nearest.begin(), nearest.end(), cmp);
        return nearest[0];
    }
    else return {-1,-1};
}
void moveTo(pair<int,int> next) {
    queue<node> q;
    node nod(cur, 0);
    bool visited[21][21];
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            visited[i][j] = false;
        }
    }
    q.push(nod);
    while (!q.empty()) {
        node now = q.front(); q.pop();
        for (int i = 0;i < 4;i++) {
            int mx = now.coor.X + dx[i];
            int my = now.coor.Y + dy[i];
            if (mx < 0 || my < 0 || mx >= n || my >= n) continue;
            if (visited[mx][my]) continue;
            if (board[mx][my] > board[cur.X][cur.Y]) continue;
            if (mx == next.X && my == next.Y) {
                cnt++;
                if (cnt == siz) {
                    cnt = 0;
                    siz++;
                }
                ans += (now.dist + 1);
                board[cur.X][cur.Y] = 0;
                cur = { mx,my };
                for (int i = 0;i < fish.size();i++) {
                    if (fish[i].X == mx && fish[i].Y == my) {
                        fish.erase(fish.begin() + i);
                        break;
                    }
                }
                board[mx][my] = siz;
                return;
            }
            else {
                visited[mx][my] = true;
                node nxt({ mx,my }, now.dist + 1);
                q.push(nxt);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            cin >> board[i][j];
            if (board[i][j] >= 1 && board[i][j] <= 6) fish.push_back({ i,j });
            else if (board[i][j] == 9) {
                cur =  { i,j };
                board[i][j] = 2;
            }
        }
    }

    while (!fish.empty()) {
        pair<int, int> nxt = findNext();
        if (nxt.X != -1) moveTo(findNext());
        else { cout << ans; return 0; }
    }
    cout << ans;
    return 0;
}