아기 상어 16236 (백준으로 C++ 공부하기 36일차)

문제

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

16236번: 아기 상어

생각

문제의 조건이 많아 천천히 읽으며 정리해야 한다. 안 그러면 이상한 풀이로 계속 풀다가 꼬인다.

1주일 정도 고민을 했지만 계속 답이 나올락 말락 안 나왔다.

그래서 다른 사람의 코드를 참고했다.

https://yulme.tistory.com/92

이 사람은 우선순위 큐로 우선순위를 연산자로 정했다. 우선순위는 거리 > 가장 위 > 가장 왼쪽 순이다.

 

이동하는 거리를 저장하는데 먹을 수 있는 물고기를 만나면 그 이동한 거리를 저장하고 다시 거리를 0으로 초기화한다.

또한 먹을 수 있는 물고기를 만나면 vst를 초기화해줘야 하는데 memset으로 손쉽게 할 수 있다.

이는 #include <cstring>에 포함되어 있다.

코드

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

struct fish {
	int dist;
	int x;
	int y;

	bool operator < (const fish &f) const {
		if (dist == f.dist) {
			if (y == f.y) {
				return x > f.x; //x값 기준으로 오름차순 (최소힙)
			}
			else return y > f.y; //y값 기준으로 오름차순 
		}
		else return dist > f.dist; //d값 기준으로 오름차순
	}
};

int dx[4] = { 0, -1, 0, 1 };
int dy[4] = { -1, 0, 1, 0 };
int map[21][21];
int vst[21][21] ={0, };
int sty, stx;

int main() {
    int n; 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) {
                sty = i;
                stx = j;
                map[i][j] = 0;
            }
        }
    }

    int size = 2;
    int sum = 0;
    int fishcnt = 0;
    int cnt = 0;
    priority_queue<fish> q;
    q.push({0, sty, stx});
    vst[sty][stx] = true;
    while(!q.empty()) {
        int dist = q.top().dist;
        int y = q.top().y;
        int x = q.top().x;
        q.pop();

        //Edible
        if(map[y][x] > 0 && map[y][x] < size) {
            fishcnt++;
            map[y][x] = 0;
            if(size == fishcnt) {
                size++;
                fishcnt = 0;
            }
            sum += dist;
            dist = 0;
            memset(vst, false, sizeof(vst));
            while (!q.empty()) q.pop();
        }
        for(int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || nx < 0 || ny > n - 1 || nx > n - 1 || vst[ny][nx]) continue;
            if (map[ny][nx] > size) continue;
            q.push({dist + 1, ny, nx});
            vst[ny][nx] = true;
        }
    }
    cout << sum;
    }
}