백준 16236 아기상어

코딩 테스트를 5일 앞두고 기출 문제를 조금씩 풀려고 한다.

푸는데 성공하면 글을 쓰겠지만, 못 풀면 이 문제 이후로 업데이트가 없을 수도..

 

알고리즘 2를 수강하면서 한 번 풀어보았던 문제여서 그래도 풀 수 있었던 것 같다.

한 번 이동이 가중치 1이고, 계속해서 가장 가까운 물고기를 찾아야 하기 때문에 bfs를 통해 풀 수 있다.

n의 크기가 최대 20이기 때문에 시간 복잡도도 충분하다.

 

무한 루프를 통해서 bfs를 계속 돌면서 먹을 수 있는 물고기를 찾는다.

만약 먹을 수 있는 물고기가 더이상 없으면 무한루프를 종료한다.

 

먹을 수 있는 물고기를 vector에 추가하고, 여러 마리가 있을 경우 row와 col을 비교하여 처리하는 것이 조금 귀찮은 문제인 것 같다.

 

물고기를 먹고 나면 dist 배열을 초기화 해주고, 그 위치에서 다시 시작하면 된다.

 

코드는 아래와 같다. 디버깅을 위한 출력문들도 주석처리 되어 있다.

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
 
int map[20][20];
int dist[20][20];
 
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,1,0,-1 };
 
int main(int argc, char** argv) {
    int n, lv = 2, exp = 0, ans = 0;
    cin >> n;
    
    queue<pair<int, int>> q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &map[i][j]);
            //시작 위치를 push
            if (map[i][j] == 9) {
                q.push(make_pair(i, j));
                dist[i][j] = 1;
                map[i][j] = 0;
            }
        }
    }
    //printf("\n");
    //먹이를 한 번 찾을 때 마다 bfs를 돌아야 하니까 무한 루프를 돈다.
    while (1) {
        vector<tuple<int, int, int>> obj;
        while (!q.empty()) {
            int row = q.front().first;
            int col = q.front().second;
            q.pop();
 
            for (int i = 0; i < 4; i++) {
                int nr = row + dr[i];
                int nc = col + dc[i];
 
                if (nr < 0 || nr >= n || nc < 0 || nc >= n)continue;
                //lv이 더 높은 물고기가 있으면 못 지나간다.
                if (lv < map[nr][nc])continue;
                //이미 지나간 곳은 안가도 된다. 최소 거리를 찾아야 하기 때문에
                if (dist[nr][nc] != 0)continue;
                //잡아 먹을 수 있으면 먹이 리스트에 저장한다.
                if (lv > map[nr][nc] && map[nr][nc] != 0) {
                    dist[nr][nc] = dist[row][col] + 1;
                    q.push(make_pair(nr, nc));
                    //먹을 수 있는 list에 추가한다.
                    obj.push_back(make_tuple(nr, nc, dist[nr][nc]));
                }
                else {
                    dist[nr][nc] = dist[row][col] + 1;
                    q.push(make_pair(nr, nc));
                }
            }
            /* 출력부분
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    printf("%d ", dist[i][j]);
                }
                printf("\n");
            }
            printf("\n");
            */
        }
        /*출력부분
        printf("bfs종료\n");
        printf("먹을 수 있는 물고기: %d\n", obj.size());
        */
        //먹을 수 있는 물고기가 없으면 종료
        if (obj.size() == 0) {
            break;
        }
        int min_idx, min_dis = 100;
        //갈 수 있는 곳을 모두 다 돌았으면 먹을 걸 고른다.
        for (int i = 0; i < obj.size(); i++) {
            //공간의 크기가 최대 20이므로 최대값을 그냥 100으로 준다.
            int row, col, dis;
            tie(row, col, dis) = obj[i];
            //최소 거리를 찾아간다.
            if (min_dis > dis) {
                min_dis = dis;
                min_idx = i;
            }//거리가 같을 경우
            else if (min_dis == dis) {
                //가장 위에 있는 물고기를 선택
                int cmp_row, cmp_col, cmp_dis;
                tie(cmp_row, cmp_col, cmp_dis) = obj[min_idx];
                if (row < cmp_row) {
                    min_idx = i;
                }
                //같은 높이에 있을 경우
                if (row == cmp_row) {
                    //가장 왼쪽에 있는 물고기를 선택
                    if (col < cmp_col) {
                        min_idx = i;
                    }
                }
            }
        }
        //가장 가까이 있는 물고기의 위치
        int objr, objc, objd;
        tie(objr, objc, objd) = obj[min_idx];
        //경험치 올라가고, 그 공간은 0으로 만든다.
        exp++;
        //level up!!
        if (exp == lv) {
            exp = 0;
            lv++;
        }
        map[objr][objc] = 0;
        //이동한 시간을 더해준다.
        ans += dist[objr][objc] - 1;
        //dist를 초기화 해준다.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = 0;
            }
        }
        //방금 물고기를 먹은 위치를 다시 시작위치로 넣어준다.
        q.push(make_pair(objr, objc));
        dist[objr][objc] = 1;
 
        /*출력부분
        //lv, exp 출력
        printf("lv: %d, exp: %d\n", lv, exp);
        printf("현재 걸린 시간: %d\n", ans);
        //바뀐 맵 출력
        printf("--------------바뀐 맵----------------\n");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                printf("%d ", map[i][j]);
            }
            printf("\n");
        }
        printf("-----------------------------\n");
        */
    }
 
    printf("%d\n", ans);
 
 
    return 0;
}