[BFS] 아기 상어 - 백준 16236번
문제 파악은 쉽게 하였으나 구현에 있어 어려움을 느꼈다. bfs 문제를 많이 풀어볼 필요가 있다.
GPT의 도움을 받아 해결
풀이Permalink
의도한 풀이 (틀린 풀이)Permalink
- 입력 받을 때 물고기의 크기가 담긴 Map 을 설정한다
map<int, vector<pair<int, int> > > mp;
mp = { 1: [(2, 0), (0, 2)] 2: ... ... 6: ... }
-
먹을 수 있는 물고기들의 위치를 배열에 담아놓기
if(vec[i][j] == 1) { feed.push_back(make_pair(i, j)); }
- 배열에서 하나씩 꺼내어 아기 상어와 물고기의 거리를 비교
- BFS를 사용하여 거리 비교
- 거리가 제일 작은 물고기로 아기 상어를 이동, 사이즈 업
- 사이즈 업시 먹을 수 있는 물고기들 배열에 추가
- 배열이 빌 때 까지 2,3,4 반복
문제점Permalink
각 먹이까지의 거리를 각각 계산하여 최소 거리를 찾는다.
- 점과 점 사이의 거리를 구하는데 BFS를 사용하는 것은 비효율적이다.
- 한 번의 BFS 탐색으로 모든 먹이의 위치를 찾는다.
⇒ 각 먹이마다 호출되어 중복된 BFS 계산이 발생
제대로된 풀이Permalink
vector<vector<int> > dist(N, vector<int>(N, -1));
거리를 넣을 수 있는 배열을 통해 제자리에서 갈 수 있는 모든 좌표의 거리를 찾는다.
EX)
- 제자리(0)를 기준으로 인접한 셀을 +1 하며 넓혀나간다.
- 사이즈가 큰 물고기가 있는 경우(장애물) 무시한다.
- 물고기가 있는 자리라면 최소 거리를 비교
if (vec[nx][ny] > 0 && vec[nx][ny] < size_v)
- 최소 거리로 자리를 이동 후 다시 BFS를 시도
코드Permalink
https://github.com/KimGyeongLock/CodingTest/blob/main/16236.cpp