[BFS&구현] 백준 16236 아기상어

 

www.acmicpc.net/problem/16236

16236번: 아기 상어

수행 시간: 3시간

 

글을 오랜만에 올리는 것 같다.. 요즘 취준때문에 바쁘기도하고 사실 알고리즘은 거의 매일 풀었는데 풀기만하고 올리지를 않아서 오늘 몰아서 올릴 것 같다.

친구와 타임어택으로 푼 골드4 수준의 삼성 SW 역량테스트 문제다. 문제자체는 크게 어려움을 느끼지 못했지만 생각해야될 부분도 많고 조건이 너무 많아서 코드를 짜는데 오래 걸렸다.

특히

                        if (time > (t + 1)) {
                            time = (t + 1);
                            f_x = nx;
                            f_y = ny;
                        }
                        else if (time == (t + 1)) {
                            if (f_x > nx) {
                                f_x = nx;
                                f_y = ny;
                            }
                            else if (f_x == nx && f_y > ny) {
                                f_y = ny;
                            }
                        }

이 부분에서 t 가아닌 t+1로 해줘야 된다는 사실은 친구가 내 코드를 봐준 후에야 알아차렸다.. 

이유는 for문 안에서 nx,ny(next x , next y)를 통해 구현되므로 현재 시간 t가 아닌 t+1로 해줘야했다.

 

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
int n;
int map[21][21];
bool visited[21][21] = { false, };
int shark = 2; //상어의 초기크기.
int shark_x, shark_y;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int min_dis, fish_x, fish_y;
int result = 0;
int eat = 0;

bool bfs(int x, int y) {
    int cnt = 0;
    int time = 10000;
    int t;
    int f_x, f_y;
    queue <pair<pair<int, int>, int>> q;
    q.push({ {x, y }, 0 });
    while (!q.empty()) {
        x = q.front().first.first;
        y = q.front().first.second;
        t = q.front().second;
        //cout << x << " " << y << t << std::endl;
        q.pop();
        for (int i = 0;i < 4;i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n) { //맵안에있고
                if (visited[nx][ny] == false && map[nx][ny] <= shark) { // 방문하지 않고, 물고기의 크기가 상어보다 작거나 같으면
                    visited[nx][ny] = 1; // 이동거리 증가시킴   
                    if (map[nx][ny] != 0 && map[nx][ny] < shark) { //먹을수 있다면?
                        if (time > (t + 1)) {
                            time = (t + 1);
                            f_x = nx;
                            f_y = ny;
                        }
                        else if (time == (t + 1)) {
                            if (f_x > nx) {
                                f_x = nx;
                                f_y = ny;
                            }
                            else if (f_x == nx && f_y > ny) {
                                f_y = ny;
                            }
                        }
                    }
                    q.push({ {nx,ny }, t + 1 }); //물고기 위치 push
                }
            }
        }
    }
       
    if (time == 10000) {
        return 0;
    }
    else {
        shark_x = f_x;
        shark_y = f_y;
        map[shark_x][shark_y] = 0;
        eat++;
        if (shark == eat) {
            shark++;
            eat = 0;
        }
        result += time;
        return 1;
    }
}

int count_fish() {
    int cnt = 0;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            if (map[i][j] > 0 && map[i][j] < shark) {
                cnt++;
            }
        }
    }
    return cnt;
}

int sol() {
    while (count_fish()) {
        memset(visited, false, sizeof(visited));
        if (!bfs(shark_x, shark_y))
            break;

    }
    return result;
}


int main() {
    cin >> n;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            cin >> map[i][j];
            if (map[i][j] == 9) {
                shark_x = i;
                shark_y = j;
                map[i][j] = 0;
            }
        }
    }
    cout << sol();
}