[Algorithm][C++] JUNGOL 4211: [swat]애벌레 키우기2

url: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=3561&sca=99 

JUNGOL

 

풀이 핵심

1. 가장 가까우면서 나보다 크기가 작은 먹이를 찾는 방법을 구현하는 것이 중요하다. (BFS로 구현)

거리가 같을 경우 행 index가 작은 순서로, 행 index가 같을 경우 열 index가 작은 순서로 탐색해야 한다. 그리고 나보다 크기가 작은 먹이를 찾았다면 위치 및 거리를 return 해줘야 한다. 여기서 나보다 작은 먹이를 찾지 못했다면 프로그램을 종료한다. 

 

거리가 같을 경우 / 행 index가 같을 경우를 고려해야 하므로 우선순위 큐를 사용했다. STL 큐는 sort에 사용할 수 없고 priority_queue를 사용하자니 연산자 오버로드 이해도가 부족해 직접 큐를 구현하고 algorithm 헤더의 sort 함수 사용하여 push 할 때마다 sorting 하는 방법으로 구현했다.

 

2. 크기가 커지는 것은 먹이를 먹은 횟수를 카운트해서 먹이를 먹은 횟수가 나의 크기와 같아지면 크기가 커지고 카운트는 0으로 초기화되도록 했다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm> // sort 함수 사용하기 위해
using namespace std;

int N;
int map[20][20];
struct POS {
	int r, c, d; // 위치, 거리
};
int row, col, body = 2, cnt; // 애벌레 위치, 크기, 먹이 먹은 횟수
const int dr[] = { 1,-1,0,0 };
const int dc[] = { 0,0,1,-1 };
POS queue[20 * 20];
int fr, re;

bool cmp(POS a, POS b) {
	if (a.d == b.d) { // 거리가 같으면
		if (a.r == b.r) {
			return a.c < b.c; // 행이 같으면
		}
		return a.r < b.r;
	}
	return a.d < b.d;
}

void push(int r, int c, int d) {
	queue[re].r = r, queue[re].c = c, queue[re++].d = d;
	sort(queue + fr, queue + re, cmp); // push 할 때마다 soritng
}

POS front() {
	return queue[fr];
}

void pop() {
	fr++;
}

bool isEmpty() {
	return fr == re;
}

inline POS get_eat_pos(int sr, int sc) {
	POS ret = { -1,-1,-1 };
	bool visit[20][20] = { 0, }; // 중복 탐색 방지
	fr = re = 0;
	visit[sr][sc] = true;
	push(sr, sc, 0);
	while (!isEmpty()) {
		POS cur = front();
		pop();
		if (map[cur.r][cur.c] && map[cur.r][cur.c] < body) {
			ret = { cur.r, cur.c, cur.d }; // 먹이 위치 및 거리 return
			break;
		}
		for (int dir = 0; dir < 4; dir++) {
			int nr = cur.r + dr[dir];
			int nc = cur.c + dc[dir];
			if (nr < 0 || nr >= N || nc < 0 || nc >= N || visit[nr][nc]) {
				continue;
			}
			if (map[nr][nc] && map[nr][nc] > body) {
				continue;
			}
			visit[nr][nc] = true;
			push(nr, nc, cur.d + 1);
		}
	}
	return ret;
}

void eat_worm(POS cur) {
	map[cur.r][cur.c] = 0; // 먹이 제거
	row = cur.r, col = cur.c; // 먹이 위치로 이동
	cnt++; // 먹이 먹은 횟 수 증가
	if (cnt == body) { // 먹이 먹은 횟 수가 크기와 같으면
		body++; // 크기 증가
		cnt = 0; // 먹이 먹은 횟 수 초기화
	}
}

int solve() {
	int ret = 0;
	while (1) {
		POS eat = get_eat_pos(row, col);
		if (eat.r == -1) { // 더 이상 애벌레보다 크기가 작은 먹이 없음
			break;
		}
		ret += eat.d;
		eat_worm(eat);
	}
	return ret;
}

int main() {
	scanf("%d", &N);
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			scanf("%d", &map[r][c]);
			if (map[r][c] == 9) {
				row = r, col = c;
				map[r][c] = 0;
			}
		}
	}
	int ans = solve();
	printf("%d", ans);
	return 0;
}

 

추후에 우선순위 큐, 힙 등 자료구조 공부 및 STL 사용법 공부를 해야겠다.