[BFS] 아기 상어 - 백준 16236번

16236번: 아기 상어

문제 파악은 쉽게 하였으나 구현에 있어 어려움을 느꼈다. bfs 문제를 많이 풀어볼 필요가 있다.

GPT의 도움을 받아 해결

풀이

의도한 풀이 (틀린 풀이)

1. 입력 받을 때 물고기의 크기가 담긴 Map 을 설정한다
   • map<int, vector<pair<int, int> > > mp;

    mp = {
     1: [(2, 0), (0, 2)]
     2: ...
     ...
     6: ...
    }
   

2. 먹을 수 있는 물고기들의 위치를 배열에 담아놓기

    if(vec[i][j] == 1) {
        feed.push_back(make_pair(i, j));
    }
   

3. 배열에서 하나씩 꺼내어 아기 상어와 물고기의 거리를 비교
   • BFS를 사용하여 거리 비교
4. 거리가 제일 작은 물고기로 아기 상어를 이동, 사이즈 업
   • 사이즈 업시 먹을 수 있는 물고기들 배열에 추가
5. 배열이 빌 때 까지 2,3,4 반복

문제점

각 먹이까지의 거리를 각각 계산하여 최소 거리를 찾는다.

• 점과 점 사이의 거리를 구하는데 BFS를 사용하는 것은 비효율적이다.
• 한 번의 BFS 탐색으로 모든 먹이의 위치를 찾는다.

⇒ 각 먹이마다 호출되어 중복된 BFS 계산이 발생

제대로된 풀이

vector<vector<int> > dist(N, vector<int>(N, -1));

거리를 넣을 수 있는 배열을 통해 제자리에서 갈 수 있는 모든 좌표의 거리를 찾는다.

EX)

• 제자리(0)를 기준으로 인접한 셀을 +1 하며 넓혀나간다.
• 사이즈가 큰 물고기가 있는 경우(장애물) 무시한다.
• 물고기가 있는 자리라면 최소 거리를 비교
  • if (vec[nx][ny] > 0 && vec[nx][ny] < size_v)
• 최소 거리로 자리를 이동 후 다시 BFS를 시도

코드

https://github.com/KimGyeongLock/CodingTest/blob/main/16236.cpp