백준 16236번: 아기상어(Python, cpp)

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

16236번: 아기 상어

---

문제 해결을 위한 과정

구현 유형에 해당하는 문제 이므로 문제에서 주어진 조건을 따라서 차분하게 작성하면 쉽게 해결할 수 있는 문제 입니다. bfs를 통해 이동할 수 있는 구역을 탐색한 후 먹을 수 있는 물고기들을 배열에 담아 정렬 후 가장 첫번째에 있는 물고기를 먹으면 되는 문제 입니다.

---

소스코드 - python

from collections import deque

def bfs(x, y, size, visited):
  q = deque()
  q.append((x, y))
  count = 0
  visited[x][y] = 1
  while q:
    for _ in range(len(q)):
      x, y = q.popleft()
      for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= n or ny >= n:
          continue
        if graph[nx][ny] <= size and visited[nx][ny] == 0:
          q.append((nx, ny))
          visited[nx][ny] = 1
          if 0 < graph[nx][ny] < size:
            eatable.append((count+1, nx, ny))
    count += 1

n = int(input())
graph = []
x = 0
y = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
size = 2 
eatable = []

for i in range(n):
  graph.append(list(map(int, input().split())))
  for j in range(n):
    if graph[i][j] == 9:
      x, y = i, j
      graph[i][j] = 0

timeInfo = 0
eatCount = 0
while True:
  visited = [[0] * n for _ in range(n)]
  bfs(x, y, size, visited)
  if len(eatable) == 0:
    print(timeInfo)
    break
  eatable.sort()
  dist, xPos, yPos = eatable[0]
  eatable = []
  x, y = xPos, yPos
  graph[x][y] = 0
  timeInfo += dist
  eatCount += 1
  if eatCount == size:
    size += 1
    eatCount = 0

---

소스코드 - c++

#include <bits/stdc++.h>

using namespace std;

int graph[20][20];
int visited[20][20];
int n;
int sizeOfShark;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
vector<tuple<int, int, int>> eatable; // 거리, x좌표, y좌표

void bfs(int xPos, int yPos) {
	queue<pair<int, int>> q;
	q.push(make_pair(xPos, yPos));
	visited[xPos][yPos] = 1;
	int num = 0;
	int distance = 0;

	while (!q.empty()) {
		num = q.size();
		for (int i = 0; i < num; i++) {
			int x = q.front().first;
			int y = q.front().second;
			q.pop();
			for (int j = 0; j < 4; j++) {
				int nx = x + dx[j];
				int ny = y + dy[j];
				if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
					continue;
				}
				if (graph[nx][ny] <= sizeOfShark && visited[nx][ny] == 0) {
					q.push(make_pair(nx, ny));
					visited[nx][ny] = 1;
					if (0 < graph[nx][ny] && graph[nx][ny] < sizeOfShark) {
						eatable.push_back(make_tuple(distance + 1, nx, ny));
					}
				}
			}
		}
		distance += 1;
	}
}
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	int x = 0, y = 0; // 상어 좌표
	sizeOfShark = 2; // 초기 상어 크기

	for (int i = 0; i < n; i++) { 
		for (int j = 0; j < n; j++) {
			cin >> graph[i][j]; // 그래프 입력 받기
			if (graph[i][j] == 9) { // 상어 위치인 경우
				x = i;
				y = j;
				graph[i][j] = 0;
			}
		}
	}

	int timeInfo = 0;
	int eatCount = 0;

	while (true) {
		fill(&visited[0][0], &visited[19][20], 0);
		bfs(x, y);
		if (eatable.size() == 0) {
			cout << timeInfo;
			break;
		}
		sort(eatable.begin(), eatable.end());
		int dist = get<0>(eatable[0]);
		int xPos = get<1>(eatable[0]);
		int yPos = get<2>(eatable[0]);
		eatable.clear();
		x = xPos;
		y = yPos;
		graph[x][y] = 0;
		timeInfo += dist;
		eatCount += 1;
		if (eatCount == sizeOfShark) {
			sizeOfShark += 1;
			eatCount = 0;
		}
	}
	return 0;
}