728x90
1. 문제 설명
17086번: 아기 상어 2
첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만
www.acmicpc.net
2. 풀이 과정
- 문제 해결의 흐름
- 안전거리 : 현재 위치한 칸과 가장 가까운 아기 상어와의 거리
- 아기상어(1)를 찾는 것이 목표이기에 대각선 방향까지 포함한 8방향 탐색을 이어나가며 아기 상어를 찾자!
- 나의 코드
#include <iostream>
#include <queue>
using namespace std;
int N, M;
int shark_map[51][51] = {};
int dx[8] = {0, 0, 1, -1, 1, -1 ,1, -1};
int dy[8] = {1, -1, 0, 0, 1, -1, -1, 1};
int result = 0;
int bfs(int row, int col) {
queue<pair<int, int> > q;
int visited[51][51] = {}; // 전부 0으로 초기화
q.push(make_pair(row, col));
visited[row][col] = 0;
while(!q.empty()) {
// 상어가 없는 위치 now에서 계속 탐색을 이어간다.
int now_row = q.front().first;
int now_col = q.front().second;
q.pop();
// 8방향 탐색
for (int i = 0; i < 8; i++) {
int new_row = now_row + dy[i];
int new_col = now_col + dx[i];
// 범위값 이탈시 continue
if (new_col < 0 || new_col >= M || new_row < 0 || new_row >= N) continue;
// 상어 발견 !!
if (shark_map[new_row][new_col] == 1) {
return visited[now_row][now_col] + 1;
}
// 상어가 없다면 계속 탐색
if (visited[new_row][new_col] == 0) {
q.push(make_pair(new_row, new_col)); // 0의 위치를 넣어준다.
visited[new_row][new_col] = visited[now_row][now_col] + 1;
}
}
}
}
int main() {
cin >> N >> M;
// 상어 위치 입력 받기
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
int val;
cin >> val;
shark_map[i][j] = val;
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (shark_map[i][j] == 0) { // 상어가 없는 위치일 경우
result = max(bfs(i, j), result); // i : row_num, j : col_num
}
}
}
cout << result;
return 0;
}
- 이 문제를 통해 얻어갈 수 있는 것들
- 문제를 항상 잘 읽자! 아기상어끼리의 거리를 구하는 문제인줄 알고 엄청 헤맸다 ㅠㅠㅠㅠㅠ....
3. 후기
문제 잘 읽자!! 문제 파악 후 문제에 대해 전반적인 나의 생각을 끄적여보는 것도 정말 좋은 습관인 듯하다.
'Algorithm > graph' 카테고리의 다른 글
[백준] 6593 상범 빌딩 C++ (0) | 2024.04.20 |
---|---|
[백준] 1303 전쟁 - 전투 C++ (0) | 2024.04.19 |
[백준] 2206 벽 부수고 이동하기 C++ (1) | 2024.04.19 |
[백준] 2178 미로 탐색 C++ (0) | 2024.04.17 |
[프로그래머스] [PCCP 기출 문제] 2번 / 석유 시추 C++ (0) | 2024.04.17 |