삼성 코딩테스트 기출_(백준)아기상어

난이도 ★★★★☆

 

문제출처

acmicpc.net/problem/16236

16236번: 아기 상어

포인트

1. bfs(최단거리 탐색)

상어는 먹을 수 있는 물고기 중, 가장 '가까이에 있는' 물고기를 먹어야 하므로, 구현을 할 때에는 상어가 먹을 수 있는 모든 물고기에 대하여 상어까지의 거리를 bfs로 탐색해서 구한다.

1-1. bfs에서 사용할 queue는 bfs 함수 내에서 선언한다. 그렇게 하지 않을 시에는, bfs를 호출할 때마다 이전 호출 때 사용했던 큐를 비워주어야 한다는 단점이 있다.

1-2. 단순히 탐색을 하는 것이 아니라, 최단 거리, 즉 depth를 구하기 위해서는 queue 사이즈가 다 될 때마다 depth를 하나씩 증가시켜주는 것을 구현해야 한다.(dist++)

 

2. 먹을 수 있는 물고기가 없는 경우

2-1. 물고기가 아예 존재하지 않는 경우 : 애초에 fishes 벡터에 아무 물고기도 담기지 않기 때문에,

if(fishes.size==0) break;

로 종료 가능하다.

2-2. 물고기는 존재하지만, 크기가 모두 상어보다 커서 먹지 못하는 경우: 상어보다 사이즈가 작은 물고기에 대해서만 거리를 구해주므로, 거리값이 갱신되지 않은 경우, 즉 minDist=INF상태로 그대로 남아있는 경우에 break가 가능하다.

2-3. 물고기도 존재하고, 크기가 상어보다 작은 물고기도 있지만, 경로가 큰 물고기에 의해 모두 막혀있는 경우 : 이 경우, 물고기들이 저장된 벡터도 존재(2-1의 반대 상황)하고, minDist값도 갱신(2-2의 반대 상황)된다. 그렇기 때문에 새로운 변수 flag를 사용한다. bfs함수 내에서, 상어를 만날 수 있는 경우에만 flag를 true값으로 반환하고, true값이 된 경우에만 minDist를 갱신하도록 한다. 따라서 flag 처리를 통해 2-2에서와 같이 거리값 갱신 여부로 break처리를 할 수 있게 된다.

 

3. 상어 이동

처리해야 할 것들이 은근 많다.

3-1. 시간을 타겟 물고기와의 거리만큼 늘려준다. (ans+=target.dist)

3-2. 원래 상어가 있던 자리를 비워준다. (map[babyShark.r][babyShark.c]=0)

3-3. 상어 위치를 저장해준다. (babyShark.r=target.r, babyShark.c=target.c)

3-4. 타겟이 있던 곳을 상어로 바꿔준다. (map[target.r][target.c]=9)

3-5. 상어 먹이 횟수를 하나 카운트해준다. cnt++

3-6. 상어가 먹은 물고기가 상어 사이즈와 같은지 체크해준다 if(cnt==babyShark.size)

3-6-1. 같을 경우, cnt=0으로 초기화해주고, babyShark.size는 +=1처리한다.

3-7. 상어 이동 후 먹이의 개수가 달라졌으므로 기존 fishes벡터를 초기화하고 다시 저장한다.

 

정답소스

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

const int INF = 987654321;
bool flag = false;

int N;
int map[25][25];
int visit[25][25];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

int ans = 0;
int dist = 0;
int minDist = INF;

struct fish {
	int r;
	int c;
	int size;
	int dist;
};

struct shark {
	int r;
	int c;
	int size;
};

vector<fish> fishes;
shark babyShark;

bool range(int r, int c) {
	if (r >= 0 && r < N&&c >= 0 && c < N)return true;
	return false;
}

void initialize() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			visit[i][j] = 0;
		}
	}
}

void bfs(int r, int c) {
	flag = false;
	visit[r][c] = 1;
	queue<pair<int, int>> q;
	q.push(make_pair(r, c));

	while (!q.empty()) {
		int sz = q.size();
		dist++;
		while (sz--) {
			r = q.front().first;
			c = q.front().second;
			q.pop();
			for (int i = 0; i < 4; i++) {
				for (int j = 0; j < 4; j++) {
					int nr = r + dy[i];
					int nc = c + dx[i];
					if (range(nr, nc) && map[nr][nc] == 9) {
						flag = true;
						return;
					}
					if (range(nr, nc) && !visit[nr][nc] && map[nr][nc] <= babyShark.size) {
						visit[nr][nc] = 1;
						q.push(make_pair(nr, nc));
					}
				}
			}
		}
	}
	return;
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			if (map[i][j] >= 1 && map[i][j] <= 6) {
				fishes.push_back({ i,j,map[i][j],0 });
			}
			else if (map[i][j] == 9) {
				babyShark = { i,j,2 };
			}
		}
	}

	int cnt = 0;

	while (true) {
		if (fishes.size() == 0)break;

		fish target = { 0,0,0,minDist };

		for (int i = 0; i < fishes.size(); i++) {
			if (fishes[i].size < babyShark.size) {
				dist = 0;
				initialize();
				bfs(fishes[i].r, fishes[i].c);
				if (flag)fishes[i].dist = dist;
				else fishes[i].dist = INF;
				if (target.dist > fishes[i].dist) {
					target = fishes[i];
					minDist = target.dist;
				}
				else if (target.dist == fishes[i].dist) {
					if (target.r > fishes[i].r)target = fishes[i];
					else if (target.r == fishes[i].r) {
						if (target.c > fishes[i].c)target = fishes[i];
					}
					minDist = target.dist;
				}
			}
		}

		if (minDist == INF)break;

		ans += target.dist;
		map[babyShark.r][babyShark.c] = 0;
		babyShark.r = target.r;
		babyShark.c = target.c;
		map[babyShark.r][babyShark.c] = 9;

		cnt++;
		if (cnt == babyShark.size) {
			babyShark.size += 1;
			cnt = 0;
		}

		fishes.clear();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] >= 1 && map[i][j] <= 6) {
					fishes.push_back({ i,j,map[i][j],0 });
				}
			}
		}

		if (fishes.size() == 0)break;
		minDist = INF;
	}
	
	cout << ans << '\n';
	return 0;
}