백준 17086번 아기 상어2(c++)

17086번: 아기 상어 2

문제 분석

문제에서의 핵심은 안전 거리의 최댓값이다. 결국 한 지점에서 갈 수 있는 상어사이의 최단 거리를 구하고, 이를 비교해야하기에 모든 경우의 수를 구하는 브루트포스 알고리즘을 사용해야 한다!

 

문제에서 말하는 안전 거리란?

- 이곳에서 말하는 안전거리란, (1)상어가 없는 위치에서 각 상어와의 거리를 구하고, (2)그 거리들 중 최솟값을 말한다.

 

여기서 더욱 중요한 부분은, 2차원 평면에서 한 점을 기준으로 8개의 인접한 모든 방향으로 이동이 가능하다! 그렇기에 너비 우선 탐색을 활용하여 왔던 길을 반복하지 않도록 하는 것이 중요하다!

ex) 처음 이동을 위로 이동한 뒤, 다시 아래로 이동하면, 2번 이동하기 전 위치에 다시 돌아오게 된다. 이런 경우가 없도록 조심해야한다.

 

결론 :

- 브루트 포스 알고리즘 + 너비 우선 탐색 알고리즘을 사용해야 한다는 것을 생각하면서 문제에 접근하기!

---

문제 풀이

주어진 2차원 평면에서 아기 상어가 존재하지 않는 모든 부분에서의 안전거리를 구하고 이에 대한 최솟값을 계산해야한다.(브루트포스)

그렇기 위해서는 입력을 받은 뒤, 2중 반복문을 통해서 0인 부분마다 안전거리를 구하면 되겠다!

---

사실 문제의 핵심은 이 너비 우선 탐색(BFS)이다.

2차원 평면에서 0인 부분의 어떤 index x, y에서 어떻게 해야 최대한 효율적으로, 시간을 줄여서 상어까지의 최단 거리를 구할 수 있을까?

 

1. 상어의 위치를 표시하는 2차원 평면과 똑같은 bool 2차원 평면을 전체 false로 초기화한다. (이미 왔었던 위치인지 확인하기 위한 장치)

2.queue<tuple>을 만들어 2차원 평면의 현재의 위치 x, y, 그리고 안전 거리 distance를 저장한다.

ex) queue<tuple<int, int, int>> shark;

=> 이를 통해서 내가 이미 이동했던 위치에 다시 이동하지 않도록 한다!

 

반복문 시작 (조건 : !queue.empty()) {

3. 이 떄, 나의 현재 위치가 상어의 위치라면,(= 좌표의 원소가 1이라면) 현재 안전 거리를 return한다.

4. 아닐 경우에는 8방향으로 이동하도록 한다. 이 때, 이동할 위치의 index가 2차원 평면의 범위를 넘지 않도록, 이미 지나온 위치는 포함하지 않도록 한다.

위 경우가 아니라면, queue에 이동할 위치와 거리를 넣어준다.

}

=> 3, 4를 반복하게 되면서 모든 경우의 안전 거리를 구할 수 있게 된다. (이동했던 위치에 다시 돌아오지 않으면서)

C++ 풀이

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

using namespace std;

int N, M;
int nx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int ny[] = { -1, 0, 1, -1, 1, -1, 0, 1 };


int Shark(int x, int y, vector<vector<int>> &area) {
	vector<vector<bool>> visited(N, vector<bool>(M, false)); // 방문 여부
	queue<tuple<int, int, int>> shark; // 현재 위치
	//1, 2

	shark.push(make_tuple(x, y, 0));
	visited[x][y] = true; // 현재 위치에서 시작하기에 방문 0

	while (!shark.empty()) {
		int a1 = get<0>(shark.front()); // 현재의 행
		int b1 = get<1>(shark.front()); // 현재의 열
		int distance = get<2>(shark.front()); // 현재 거리

		shark.pop();

		if (area[a1][b1] == 1) // 현지 있는 위치가 아기 상어 위치라면
			return distance;

		for (int i = 0; i < 8; i++) { // 3, 4
			int a2 = a1 + nx[i]; // 이동할 행
			int b2 = b1 + ny[i]; // 이동할 열

			if (a2 < 0 || b2 < 0 || a2 == N || b2 == M) // 범위 초과일 경우
				continue;
			if (visited[a2][b2] == true) // 이미 왔던 위치일 경우
				continue;

			// 안왔던 곳이기에 방문 0, queue에 새로운 값 넣음.
			visited[a2][b2] = true;
			shark.push(make_tuple(a2, b2, distance + 1));
		}

	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int max_length = 0; // 안전 거리 최댓값

	cin >> N >> M;
	vector<vector<int>> area(N, vector<int>(M, 0));

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> area[i][j];
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (area[i][j] == 0) {
				max_length = max(max_length, Shark(i, j, area));
			}
		}
	}

	cout << max_length;
	return 0;
}

---

사실 이 정답을 풀기 전에 수많은 시행착오가 있었다..

BFS임을 간과한 채, 이동거리를 파라미터로 넣고 계속해서 count하며 현재의 최솟값보다 많이 이동하면 return하도록 하고, 안전거리의 최댓값을 계산하였다... 심지어 DFS로 풀었기에 시간 초과가 발생했으니... 틀린 답을 보면서 한번 더 공부해보시는 것도 추천드립니다!

틀린 정답!!!!!

#include <iostream>
#include <vector>

using namespace std;

int N, M, shark = 0;
int shortroad = 50;



void safe(int x, int y, int cnt, vector<vector<int>> &vec) {
	if (x < 0 || y < 0 || x == N || y == M || shortroad <= cnt)
		return;
	
	if (vec[x][y] == 1) {// 상어가 있을 경우
		if (shortroad > cnt) {
			shortroad = cnt;
			return;
		}
	}
	
	if (vec[x][y] == 0) {// 상어가 잇는 곳이 아닐경우
		cnt++;
		safe(x + 1, y, cnt, vec);
		safe(x, y + 1, cnt, vec);
		safe(x + 1, y + 1, cnt, vec);
		safe(x - 1, y + 1, cnt, vec);
		safe(x + 1, y - 1, cnt, vec);
		safe(x - 1, y, cnt, vec);
		safe(x, y - 1, cnt, vec);
		safe(x - 1, y - 1, cnt, vec);
	}

}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M;
	vector<vector<int>> vec(N, vector<int>(M, 0));

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> vec[i][j];
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (vec[i][j] == 0) {
				safe(i, j, 0, vec);
				if (shark < shortroad) {
					shark = shortroad;
				}
				shortroad = 50;
			}
		}
	}

	cout << shark;
	return 0;
}

코드 리뷰는 언제나 환영입니다!