[BOJ]백준 19236번: 청소년 상어 풀이 및 코드

www.acmicpc.net/problem/19237

19237번: 어른 상어

스타트 택시와 함께 반례 찾기에 까다로운 문제!!

이런 구현 문제는 문제를 잘 읽고 수행해야 할 과정들을 순서대로 했는지 점검하는게 가장 중요한 듯 하다 😢

상어의 이동에 관한 것은 홈페이지에 잘 설명되어 있으니 생략하고....

주의해야 할 것은 한 턴에 무슨 순서로? 진행되느냐!!이다

1. 냄새가 없는 칸 탐색 후 그런 칸이 없다면 냄새가 있는 칸 중 내가 있던 칸으로 가기

2. 냄새를 뿌리고 없애는 순서

 

냄새는 뿌리는 순서는 

1. 초기 모든 상어가 시작하기 전

2. 각각 상어의 이동이 끝난 후

에 뿌려주고, 감소는 모든 상어의 이동이 끝났을 때 해줘야 한당

 

나는 카운트 배열을 이동해서 상어의 이동을 오름차순으로 처리해주면서, 이미 해당 칸에 상어가 있다면 다음 상어는 사라지도록 해주엇다

 

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef struct { int n, d, x, y; }shark;
typedef struct { int num, sm; }space;
vector<shark> v;
space map[21][21];
int n, m, k,ans, dx[] = { 0,0,0,-1,1 }, dy[] = {0,-1,1,0,0};
int dir[405][5][4],cnt[21][21];
bool cmp(shark a, shark b) { return a.n < b.n; }
bool safe(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; }
int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < n; i++)
		for (int j = 0, x; j < n; j++) {
			scanf("%d", &x);
			if (x)
				v.push_back({ x,0,j,i });
		}
	sort(v.begin(), v.end(),cmp);
	for (int i = 0, d; i < m; i++)
		scanf("%d", &v[i].d);
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= 4; j++)
			for (int l = 0; l < 4; l++)
				scanf("%d", &dir[i][j][l]);
	for (auto cur : v)map[cur.y][cur.x] = { cur.n,k };
	while (v.size() != 1) {
		vector<shark>::iterator it; ans++;
		if (ans > 1000) { printf("-1"); return 0; }
		fill(&cnt[0][0], &cnt[20][21], 0);
		for (it = v.begin(); it != v.end();) {
			bool b = 0;
			for (int i = 0; i < 4; i++) {
				int nd = dir[it->n][it->d][i];
				int nx = it->x + dx[nd], ny = it->y + dy[nd];

				if (safe(nx, ny) && !map[ny][nx].sm) {
					*it = { it->n,nd,nx,ny };
					b = 1; break;
				}
			}
			if (!b)for (int i = 0; i < 4; i++) {
				int nd = dir[it->n][it->d][i];
				int nx = it->x + dx[nd], ny = it->y + dy[nd];

				if (safe(nx,ny)&&map[ny][nx].num == it->n) {
					*it = { it->n,nd,nx,ny };
					break;
				}
			}
			if (cnt[it->y][it->x])
				it = v.erase(it);
			else {
				cnt[it->y][it->x] = 1;
				it++;
			}
		}
		for(int i=0;i<n;i++)
			for (int j = 0; j < n; j++)
				if (map[i][j].sm) {
					map[i][j].sm--;
					if (!map[i][j].sm)map[i][j] = { 0,0 };
				}
		for (auto cur : v)map[cur.y][cur.x] = { cur.n,k };
	}printf("%d", ans);
	return 0;
}

런타임에러가 발생할 수도 있으니 범위 체크와 배열인덱스 체크는 꼼꼼히 해주도록 하자 ^.^