[벡준] 17086 아기 상어 2 C++

1. 문제 설명

• 링크 : https://www.acmicpc.net/problem/17086

17086번: 아기 상어 2

---

2. 풀이 과정

• 문제 해결의 흐름 
  1. 안전거리 : 현재 위치한 칸과 가장 가까운 아기 상어와의 거리 
  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. 후기 

 문제 잘 읽자!! 문제 파악 후 문제에 대해 전반적인 나의 생각을 끄적여보는 것도 정말 좋은 습관인 듯하다.