Muscardinus

아기상어 본문

알고리즘 문제/[삼성 SW 역량 테스트 기출 문제]

아기상어

Muscardinus 2020. 9. 1. 20:41
728x90

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

 

16236번: 아기 상어

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

www.acmicpc.net

 

#include <iostream>
#include <queue>

using namespace std;

int n;
int map[20][20];
int ch[20][20];
int res = 0;

int dy[] = { 1,-1,0,0 };
int dx[] = { 0,0,1,-1 };

struct Shark {
	int x, y, s, ate;
	void sizeUp() {
		s++;
		ate = 0;
	}
};

struct State {
	int x, y, dis;
	State(int a, int b, int c) {
		y = a; x = b; dis = c;
	}
	bool operator<(const State &b) const{
		if (dis == b.dis) {
			if (y == b.y) return x > b.x;
			else return y > b.y;
		}
		else return dis > b.dis;
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n;
	priority_queue<State> Q;
	Shark shark;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			cin >> map[y][x];
			if (map[y][x] == 9) {
				shark.y = y; shark.x = x;
				map[y][x] = 0;
			}
		}
	}
	Q.push(State(shark.y, shark.x, 0));
	shark.s = 2;
	shark.ate = 0;
	while (!Q.empty()) {
		State tmp = Q.top();
		Q.pop();
		int y = tmp.y;
		int x = tmp.x;
		int dis = tmp.dis;
		if (map[y][x] && map[y][x] < shark.s) {
			shark.y = y;
			shark.x = x;
			shark.ate++;
			if (shark.ate >= shark.s) shark.sizeUp();
			map[y][x] = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					ch[i][j] = 0;
				}
			}
			while (!Q.empty()) Q.pop();
			res = tmp.dis;
		}
		for (int dir = 0; dir < 4; dir++) {
			int ny = y + dy[dir];
			int nx = x + dx[dir];
			if (ny<0 || ny>=n || nx<0 || nx>=n || map[ny][nx] > shark.s || ch[ny][nx]>0) continue;
			Q.push(State(ny, nx, dis + 1));
			ch[ny][nx] = 1;
		}
	}
	cout << res << "\n";
	return 0;
}
728x90

'알고리즘 문제 > [삼성 SW 역량 테스트 기출 문제]' 카테고리의 다른 글

이차원 배열과 연산  (0) 2020.09.03
미세먼지 안녕!  (0) 2020.09.02
나무 제테크  (0) 2020.09.01
인구 이동  (0) 2020.08.31
치킨 배달  (0) 2020.08.30
Comments