[백준] 17086 - 아기 상어 2 (C++)

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

N × M 크기의 공간에 아기 상어가 여러 마리 있고, 한 칸에는 아기 상어가 최대 1마리만 존재한다.

• 어떤 칸의 안전 거리 = 그 칸과 가장 가까운 아기 상어의 거리
• 두 칸의 거리 = 하나의 칸에서 다른 칸으로 가기 위해 지나야 하는 칸의 수

이동은 인접한 8방향(대각선 포함)이 가능하고, 안전 거리가 가장 큰 칸을 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 2 ≤ N, M ≤ 50
• 0은 빈칸, 1은 아기 상어가 있는 칸 (각각 1개 이상)

 

칸마다 가장 가까운 아기 상어와의 거리를 구해야하므로 bfs 알고리즘을 사용해야 한다. 인접한 4방향이 아닌 8방향인 것도 고려해서 이동해야 한다. N과 M이 작아서 시간 안에 충분히 가능하다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N, M, 공간 정보 입력 받기
2. 아기 상어가 없는 칸마다 bfs 함수를 돌려 안전 거리의 최댓값 갱신하기
3. 안전 거리의 최댓값 출력하기

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define pii pair<int,int>

int n,m,board[50][50],mx=0,dx[8]={0,0,-1,-1,-1,1,1,1},dy[8]={-1,1,-1,0,1,-1,0,1};

void bfs(int a, int b, int d) {
    bool visit[50][50];
    fill(&visit[0][0], &visit[50][0], false);
    queue<pair<int,pii>> q;
    q.push({d,{a,b}});
    visit[a][b] = true;
    while (!q.empty()) {
        pair<int,pii> cur = q.front();
        q.pop();
        for (int i=0; i<8; i++) {
            int cx=cur.second.first+dx[i],cy=cur.second.second+dy[i];
            if (cx<0 || cx>=n || cy<0 || cy>=m || visit[cx][cy]) continue;
            if (board[cx][cy]==1) {
                mx = max(mx,cur.first+1);
                return;
            }
            q.push({cur.first+1,{cx,cy}});
            visit[cx][cy] = true;
        }
    }
}

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

    cin >> n >> m;
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
            cin >> board[i][j];

    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
            if (board[i][j]==0)
                bfs(i,j,0);

    cout << mx;
}