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

최대 1 분 소요

16236번: 아기 상어

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

GPT의 도움을 받아 해결

풀이Permalink

의도한 풀이 (틀린 풀이)Permalink

  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 반복

문제점Permalink

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

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

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

제대로된 풀이Permalink

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

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

EX)

Untitled

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

코드Permalink

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

카테고리:

업데이트: