16236 아기상어

16236 아기상어

 

 

문제에서 주어지는 조건대로 구현 하면 된다.

 

 

#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;

struct Node {
	int x, y;
	Node(){}
	Node(int x,int y):x(x),y(y){}
};

struct Next {
	int x, y, diff;
	Next(){}
	Next(int x, int y, int d):x(x),y(y),diff(d){}
};

int n, cx, cy, time, sz, cnt;
int map[20][20];
int check[20][20];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
Next v[400];
int nIdx;

void bfs() {
	check[cx][cy] = 1;
	queue<Node> q;

	q.push(Node(cx, cy));

	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		q.pop();

		//상어보다 작은 물고기 찾음
		if (map[x][y] != 0 && map[x][y] < sz) {
			v[nIdx++] = Next(x, y, check[x][y] - 1);
		}

		for (int i = 0; i < 4; i++) {
			int ax = x + dx[i];
			int ay = y + dy[i];

			if (ax >= 0 && ay >= 0 && ax < n&&ay < n && check[ax][ay] == 0) {
				if (map[ax][ay] <= sz) {
					q.push(Node(ax, ay));
					check[ax][ay] = check[x][y] + 1;
				}
			}
		}
	}
}

void clear() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			check[i][j] = false;
		}
	}
}

int main() {
	scanf("%d", &n);

	time = 0;
	sz = 2;
	cnt = 2;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &map[i][j]);
			//cx, cy = 현재 아기상어 위치
			if (map[i][j] == 9) {
				cx = i;
				cy = j;
			}
		}
	}

	while (true) {
		//배열 초기화
		clear();
		nIdx = 0;

		//탐색
		bfs();
		
		//먹을 수 있는 물고기 없으면 종료
		if (nIdx == 0) break;

		//가장 가깝고 위에있으면서 왼쪽에 있는 물고기 찾음
		Next nn = v[0];
		for (int i = 1; i < nIdx; i++) {
			if (nn.diff > v[i].diff) {
				nn = v[i];
			}
			else if (nn.diff == v[i].diff) {
				if (nn.x > v[i].x) {
					nn = v[i];
				}
				else if (nn.x == v[i].x) {
					if (nn.y > v[i].y) {
						nn = v[i];
					}
				}
			}
		}

		cnt--;
		if (cnt == 0) {
			sz++;
			cnt = sz;
		}

		//해당칸으로 이동 및 맵 최신화
		map[nn.x][nn.y] = 9;
		map[cx][cy] = 0;

		cx = nn.x;
		cy = nn.y;

		time += nn.diff;
	}

	printf("%d\n", time);
}