[백준]16236_아기 상어

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

Solved

✔ 알고리즘 분류: 구현, BFS, 시뮬레이션
✔ 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 가는 방법=> BFS에서 반복문 안의 구현
✔ 이 문제는 코드의 주석을 읽으며 구현 방법을 생각해보자.

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

int board[20][20];
int shark = 2, fish=0;
int n;
int min_dist, min_x, min_y;
int direction[4][2] = { {-1,0},{0,-1},{0,1},{1,0} }; //북서남동
int visit[20][20] = { 0 };
int eat = 0;


void init() {
	min_dist = 401;
	min_x = 21;
	min_y = 21;
	memset(visit, -1, sizeof(visit));
}

void bfs(int startX, int startY) {
	queue<pair<int, int>> q;
	int togoX, togoY;

	q.push(make_pair(startX, startY));
	visit[startX][startY] = 0; //방문여부가 아닌 이동거리 저장

	while (q.empty() == false) {
		pair<int, int> v = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			togoX = v.first + direction[i][0];
			togoY = v.second + direction[i][1];
            //다음 좌표가 범위 밖이라면
			if (togoX < 0 || togoX >= n || togoY < 0 || togoY >= n) continue;
            //다음 좌표를 방문한 적이 있거나 다음 좌표에 상어보다 큰 물고기가 있다면
			if (visit[togoX][togoY] != -1 || shark < board[togoX][togoY]) continue;
			visit[togoX][togoY] = visit[v.first][v.second] + 1;

			if (board[togoX][togoY] < shark && board[togoX][togoY] != 0) {
            	//가장 가까운 물고기를 먹으러 간다.
				if (min_dist > visit[togoX][togoY]) {
					min_x = togoX;
					min_y = togoY;
					min_dist = visit[togoX][togoY];
				}
                //거리가 가까운 물고기가 많다면
				else if (min_dist == visit[togoX][togoY]) {
					if (min_x == togoX) { // x좌표가 같다면 가장 왼쪽 물고기
						if (min_y > togoY) {
							min_x = togoX;
							min_y = togoY;
						}
					}
					else if (min_x > togoX) { //가장 위에 있는 물고기
						min_x = togoX;
						min_y = togoY;
					}
				}
			}
			q.push(make_pair(togoX, togoY));
		}
	}
}


int main() {
	int startX, startY, time=0;
	int answer = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];
			if (board[i][j] == 9) {
				startX = i;
				startY = j;
				board[i][j] = 0;
			}
			else if (board[i][j] != 0)
				fish++;
		}
	}

	while (1) {
		init();
		//bfs 1회에 먹을 수 있는, 가장 가까운 물고기의 위치 min_x,min_y와 거리 min_dist를 구한다.
		bfs(startX, startY);
        //min_x와 min_y가 초기 상태 그대로라면 먹을 것이 없으므로 정답 출력
		if (min_x != 21 && min_y != 21) {
			answer += min_dist;
			eat++;
			if (eat == shark) {
				shark++;
				eat = 0;
			}
			fish--;
			startX = min_x;
			startY = min_y;
			board[startX][startY] = 0;
		}
		else
			break;
	}
	cout << answer;
}