16236 아기상어

 

 

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

16236번: 아기 상어

 

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

// 상어 위치 및 시간 저장 구조체
struct SHARK {
	int y, x, t;
};


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

SHARK shark;
int shark_size, shark_eat;

int n;
int arr[30][30];


void BFS() {

	bool is_exists = true; // 먹을 물고기 있는지 판별하는 플래그
	
    // 매 시간마다
	while(is_exists) {
		queue <SHARK> q;
		is_exists = false; // set init as False
		int visit[30][30] = {false, }; // 방문체크 초기화

		q.push(shark); // 1. 상어 위치 넣고, 방문체크
		visit[shark.y][shark.x] = true; 

		SHARK target; // 먹을 물고기
		target.t = -1; // set init as False
		target.y = 30; // set init as 가장 선택후순위가 되는 max 값 넣기

		while (!q.empty()) {
			SHARK cur = q.front();
			q.pop();

			// 처음 도는 경우가 아니고 && 현재 시간보다 타겟 시간이 넘으면 체크할 필요가 없으니까 탈출
			if(target.t != -1 && target.t < cur.t)
				break;

			// 먹을 수 있으면 compare target with cur
            // 가장 먼저 먹을 물고기를 target 으로 선택한다.
			if(arr[cur.y][cur.x] != 0 && arr[cur.y][cur.x] < shark_size) {
				is_exists = true;
                // 비교순위, 1.상 2.좌
				if(cur.y < target.y || (cur.y == target.y && cur.x < target.x)) {
					target = cur;
				}
			}

			// 다음 서칭 가능한 위치들 q 삽입
			for(int i=0; i<4; i++) {
				SHARK next;
				next.y = cur.y + dy[i];
				next.x = cur.x + dx[i];
                // 다음서칭 시간은 cur.t + 1
				next.t = cur.t + 1;

				if(next.y < 0 || next.y >= n || next.x < 0 || next.x >= n)
					continue;
                    
				// 방문확인, 이동 가능한 맵인지 확인
				if(visit[next.y][next.x] == false && arr[next.y][next.x] <= shark_size) {
					visit[next.y][next.x] = true;
					q.push(next);
				}
			}
		}
        // 먹을 물고기가 있으면
		if (is_exists) {
			shark_eat++; 
			shark = target; // 상어 위치 물고기 위치로 변경
            // 상어크기 변경
			if(shark_eat == shark_size) {
				shark_size++;
				shark_eat = 0;
			}
            // 먹은 물고기 위치 0 로 변경
			arr[shark.y][shark.x] = 0;
		}
 	}


}


int main(int argv, char ** argc) {

	scanf("%d", &n);

	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++) {
			scanf("%1d", &arr[i][j]);

			if(arr[i][j] == 9) {
				shark.y = i;
				shark.x = j;
				shark.t = 0;

				shark_size = 2; shark_eat = 0;

				arr[i][j] = 0;
			}

		}

	BFS();
	
    // 다 돌고 나면 더 이상 먹을 수 있는 것이 없음
    // 결과 시간 출력
	printf("%d\n", shark.t);

	return 0;
}

 

 

 

시간 카운트의 위치 잘 설정하기

while 을 이중으로 돌리는 것이 좀 이래도 되나 싶었지만 20 * 20 맵이라 가능한듯.

각 시간별 모든 경우 서칭은 BFS

 

1. queue <SHARK> q, visit[][] 을 매 초마다 init 

2. target.t target.y 초기화

3. target.t < cur.t 비교하여, 매 시간 설정 queue value 들만 체크하도록 (아닐경우 break) 하는 것 

4. shark 구조체 설정