[C++] 16236 - 아기 상어 (골드 3)

1. 문제 설명

16236번: 아기 상어

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가

www.acmicpc.net

문제 조건 하나 잘못 읽었다가 시간 왕창 빼앗김..

난이도 자체는 어렵지 않다.

2. 아이디어

bfs 돌리면 되겠다 싶은 건 보자마자 알 수 있을 거고

문제는 움직일 target이 여러 개가 존재할 수 있기 때문에, 그 중 최적값만 찾아야 한다.

흐름은 다음과 같이 진행될 것이다.

현재 위치에서 bfs로 다음 먹이의 위치와 위치까지 이동 거리를 계산한다.
- 만약, 이동하지 않았다면 반복문을 멈춘다.
아기 상어를 다음 먹이의 위치로 이동시킨다.
먹이를 먹은 횟수가 현재 사이즈에 도달하면 size+1

코드로 표현하면 다음과 같다.

typedef struct BabyShark {
    int y, x, size = 2, totalCnt = 0, moveCnt = 0, point = 0;
} BabyShark;
BabyShark babyShark;

int main() {
    ...

    while (true) {
        coord nxtCoord = searchFeed();

        if (nxtCoord.y == 250)
            break;
        updateShark(nxtCoord);
    }

    cout << babyShark.totalCnt << "\n";

    return 0;
}

void updateShark(coord nxtCoord) {
    map[nxtCoord.y][nxtCoord.x] = 0; // 맵에서 먹이 제거
    babyShark.totalCnt += nxtCoord.moveCnt; // 전체 이동 횟수 갱신
    babyShark.moveCnt = 0; // 먹이를 먹기 위한 이동 횟수 초기화
    babyShark.y = nxtCoord.y; // 먹이의 좌표로 이동
    babyShark.x = nxtCoord.x;
    
    if (++babyShark.point == babyShark.size) { // size 증가
        babyShark.point = 0;
        ++babyShark.size;
    }
}

이제 bfs를 구현해서 먹이의 위치만 찾으면 되는데, 코드가 너무 지저분해서 마음에 안 든다. --

1️⃣ 유효성 검사

if (!inRange(ny, nx)) continue;
if (visited[ny][nx]) continue;
if (now.size < map[ny][nx]) continue;

3가지 케이스에 대해서는 queue에 다음 정점으로 이동하지 않는다.

범위를 벗어난 경우
방문한 정점
아기 상어의 size보다 큰 물고기가 있는 정점의 경우

2️⃣ 이동 거리 계산

위의 예외 케이스를 반영하여 bfs 도입 부분을 작성해보면 다음과 같다.

typedef struct coord {
    int y = 250, x = 250, moveCnt = 987654321;
} coord;

coord searchFeed() {
    queue<BabyShark> q; q.push(babyShark);
    bool visited[25][25] = {false, };
    visited[babyShark.y][babyShark.x] = true;

    coord res;

    while (q.size() > 0) {
        BabyShark now = q.front();
        q.pop();

        int y = now.y, x = now.x;
        ++now.moveCnt; // 정점 방문 시, 이동 횟수 +1

        for (pii dydx : moveVector) {
            int ny = y + dydx.first;
            int nx = x + dydx.second;

            if (!inRange(ny, nx)) continue;
            if (visited[ny][nx]) continue;
            if (now.size < map[ny][nx]) continue;
            
            ...
        }
    }
    
    return res;
}

참고로 최종적으로 targeting한 먹이의 좌표와 해당 거리를 계산하기 위해 coord 구조체를 사용했다.

처음에는 사실 bfs 할 때마다 이동 횟수를 카운트 해주지 않고, 좌표만으로 거리를 계산했었다.

그랬더니 다음과 같은 문제가 발생했다.

위의 맵에서 (5,5)위치에서 가장 가까운 먹이는 (0,0)에 위치한다.

그런데 거리 계산을 좌표로 구해버리면 (0,5)를 가장 가까운 먹이로 판단해버린다.

따라서 정점 방문 횟수를 계산해서 이동 거리를 계산해야 할 필요가 있다.

2️⃣ 먹이 선택

coord searchFeed() {
    ...

    while (q.size() > 0) {
        ...

        for (pii dydx : moveVector) {
            ...

            if (map[ny][nx] != 0 && now.size > map[ny][nx]) {
                if (now.moveCnt < res.moveCnt) {
                    res.y = ny;
                    res.x = nx;
                    res.moveCnt = now.moveCnt;
                } else if (now.moveCnt == res.moveCnt) {
                    if (ny < res.y) {
                        res.y = ny;
                        res.x = nx;
                    } else if (ny == res.y && nx < res.x) {
                        res.y = ny;
                        res.x = nx;
                    }
                }  
            }

            ...
        }
    }

    return res;
}

여기가 가장 마음에 안 드는 코드가 나온 구간인데, 플로우는 다음과 같다.

더 가까운 먹이가 있다면, 해당 좌표를 타겟팅한다.
가까운 먹이가 많다면,
1. row의 값이 더 작은 먹이를 타겟팅 한다.
2. row의 값이 같다면 col의 값이 더 작은 먹이를 타겟팅한다.

여기 리팩토링 하려고 하긴 했으나, 생각보다 이 문제에 시간을 많이 빼앗겼다는 점(50분 소모)과

지금 할 일이 너무 많아서 개발도 못 하고 있는데 진짜 열 받네. 하

여튼 이 뒤에는 방문처리 해주고, 현재 상어 위치를 다음 위치로 바꾼 다음 다시 큐에 넣어주면 된다.

문제가 너무 친절해서 하라는 것만 잘 하면 풀 수 있는 문젠데,

바보같이 가장 가까운 물고기를 먼저 선택해야 한다는 조건을 못 봐서 20분을 더 썼다.

문제 잘 읽자.

3. 코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
typedef pair<int, int> pii;

int n;
int map[25][25];
vector<pii> moveVector = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

typedef struct BabyShark {
    int y, x, size = 2, totalCnt = 0, moveCnt = 0, point = 0;
} BabyShark;
BabyShark babyShark;

typedef struct coord {
    int y = 250, x = 250, moveCnt = 987654321;
} coord;

void init();
coord searchFeed();
void updateShark(coord);

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    init();

    while (true) {
        coord nxtCoord = searchFeed();

        if (nxtCoord.y == 250)
            break;
        updateShark(nxtCoord);
    }

    cout << babyShark.totalCnt << "\n";

    return 0;
}

void init() {
    cin >> n;

    for (int i=0; i<n; ++i) for (int j=0; j<n; ++j) {
        int tmp; cin >> tmp;
        map[i][j] = tmp;

        if (tmp == 9) {
            babyShark.y = i; babyShark.x = j;
            map[i][j] = 0;
        }
    }
}

void updateShark(coord nxtCoord) {
    map[nxtCoord.y][nxtCoord.x] = 0;
    babyShark.totalCnt += nxtCoord.moveCnt;
    babyShark.moveCnt = 0;
    babyShark.y = nxtCoord.y;
    babyShark.x = nxtCoord.x;
    
    if (++babyShark.point == babyShark.size) {
        babyShark.point = 0;
        ++babyShark.size;
    }
}

bool inRange(int y, int x) {
    return (0 <= y && y < n && 0 <= x && x < n);
}

coord searchFeed() {
    queue<BabyShark> q; q.push(babyShark);
    bool visited[25][25] = {false, };
    int nxtY = 500, nxtX = 500;
    visited[babyShark.y][babyShark.x] = true;

    coord res;

    while (q.size() > 0) {
        BabyShark now = q.front();
        q.pop();

        int y = now.y, x = now.x;
        ++now.moveCnt;

        for (pii dydx : moveVector) {
            int ny = y + dydx.first;
            int nx = x + dydx.second;

            if (!inRange(ny, nx)) continue;
            if (visited[ny][nx]) continue;
            if (now.size < map[ny][nx]) continue;

            if (map[ny][nx] != 0 && now.size > map[ny][nx]) {
                if (now.moveCnt < res.moveCnt) {
                    res.y = ny;
                    res.x = nx;
                    res.moveCnt = now.moveCnt;
                } else if (now.moveCnt == res.moveCnt) {
                    if (ny < res.y) {
                        res.y = ny;
                        res.x = nx;
                    } else if (ny == res.y && nx < res.x) {
                        res.y = ny;
                        res.x = nx;
                    }
                }  
            }

            visited[ny][nx] = true;
            now.y = ny; now.x = nx;
            q.push(now);
        }
    }

    return res;
}

저작자표시 비영리

1. 문제 설명

2. 아이디어

3. 코드

티스토리툴바