백준 17086 c++ "아기 상어 2" -PlusUltraCode-

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

[필자 사고]

재미난 문제다.

BFS문제이다 . 이 문제만의 재미난 점은 

특정 지점에서 상어의 최소 거리를 각 좌표를 구하고 최대값을 구하면 된다. 

 

필자는 해당 부분을 모든 좌표로 브루트포스로 진행했고 최단 거리 구하는 방법은 BFS로 구했따. 

 

아래는 자세한 코드 해설이다.

 

[코드 해설]

Input()

• 역할: 문제에서 주어진 공간의 크기와 상태를 입력받습니다.
• 동작:
  1. N, M을 입력받습니다.
  2. arr를 N×M 크기로 초기화합니다.
  3. dist를 arr와 같은 크기로 초기화합니다.
  4. 이어서 N줄에 걸쳐서 공간 상태(0: 빈 칸, 1: 아기 상어)를 입력받아 arr에 저장합니다.

---

isInside(int sero, int garo)

• 역할: 좌표 (sero, garo)가 공간 범위 안에 있는지 확인합니다.
• 반환값:
  • true: 범위 안에 있음
  • false: 범위 밖임

---

BFS(int sero, int garo)

• 역할: 특정 빈 칸 (sero, garo)에서 시작해 가장 가까운 아기 상어까지의 거리를 BFS로 구합니다.
• 동작:
  1. 큐를 준비하고 (sero, garo, 0)을 넣습니다.
  2. visited 배열을 N×M 크기로 초기화하고, 시작점을 방문 처리합니다.
  3. 큐가 빌 때까지 탐색을 반복합니다.
     • 큐에서 현재 좌표와 거리(count)를 꺼냅니다.
     • 만약 현재 칸에 아기 상어(arr[nowSero][nowGaro] == 1)가 있으면, 시작점 (sero, garo)에서 상어까지의 최소 거리임이 확정되므로 dist[sero][garo]에 기록하고 함수를 종료합니다.
     • 인접한 8방향을 확인합니다.
       • 범위 밖이면 건너뜁니다.
       • 이미 방문한 칸이면 건너뜁니다.
       • 조건을 만족하면 방문 처리하고 거리+1을 큐에 넣습니다.

---

Game_Start()

• 역할: 전체 탐색을 관리하고 결과를 출력합니다.
• 동작:
  1. 전체 공간을 순회하면서 빈 칸(arr[i][k] == 0)일 때 BFS(i, k)를 호출합니다.
     → 이 과정을 통해 각 빈 칸에서 가까운 상어까지의 거리를 dist에 저장합니다.
  2. 전체 dist 배열을 확인하면서 최댓값을 찾습니다.
  3. 최댓값을 출력합니다.

---

main()

• 역할: 프로그램 시작점입니다.
• 동작:
  1. Input()으로 입력을 받습니다.
  2. Game_Start()를 실행하여 결과를 출력합니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef struct Node {
	int sero;
	int garo;
	int count;
};

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

int N, M;
vector<vector<int>> arr;
vector<vector<int>> dist;
vector<vector<bool>> visited;
void Input() {
	cin >> N >> M;
	arr.assign(N, vector<int>(M));
	dist = arr;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			cin >> arr[i][k];
		}
	}
}

bool isInside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < M)return true;
	return false;
}

void BFS(int sero, int garo) {
	queue<Node> myQueue;
	myQueue.push({ sero,garo,0 });
	visited.assign(N, vector<bool>(M, false));
	visited[sero][garo] = true;

	while (!myQueue.empty()) {
		int nowSero = myQueue.front().sero;
		int nowGaro = myQueue.front().garo;
		int nowCount = myQueue.front().count;
		myQueue.pop();
		if (arr[nowSero][nowGaro] == 1) {
			dist[sero][garo] = nowCount;
			return;
		}

		for (int i = 0; i < 8; i++) {
			int nextSero = nowSero + dy[i];
			int nextGaro = nowGaro + dx[i];

			if (isInside(nextSero, nextGaro)==false)continue;
			if (visited[nextSero][nextGaro])continue;
			visited[nextSero][nextGaro] = true;
			myQueue.push({ nextSero,nextGaro,nowCount + 1 });
		}
	}
}

void Game_Start() {
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			if (arr[i][k] == 1)continue;
			BFS(i, k);
		}
	}

	int maxResult = -1;

	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			if (maxResult < dist[i][k]) {
				maxResult = dist[i][k];
			}
		}
	}
	cout << maxResult;
}

int main(void) {
	Input();
	Game_Start();
}