[백준 16236번] 아기 상어

이 문제는 삼성 SW 역량 테스트 기출문제 입니다.

난이도: 골드 5

문제 링크: www.acmicpc.net/problem/16236

16236번: 아기 상어

백준 16236번: 아기 상어

BFS를 이용한 탐색을 핵심으로 하는 문제입니다.

BFS에 대한 이론적 배경은 여기를 참고하세요.

BFS를 실제로 이용하여 문제를 푸는 접근법이 아직 생소하여, 인터넷 검색을 많이 활용했습니다.

 

문제가 내용이 긴데, 요약하면 아래와 같습니다.

• 상어는 본인보다 작은 물고기만 잡아먹을 수 있다.
• 상어는 빈 공간 혹은 자기보다 작거나 같은 크기의 물고기가 있는 곳은 지나갈 수 있다.
• 상어가 자기 크기만큼의 물고기를 먹으면 크기가 1 증가한다. 예를 들어, 크기가 3이 된 후 물고기를 3번 잡아먹으면 크기가 4가 된다.
• 각 칸의 이동시간은 1이며, 물고기를 잡아먹는 시간은 0이다.

위 조건 하에, 먹을 수 있는 물고기를 모두 먹은 후에 이동 시간의 총합을 출력하면 됩니다.

 

제가 접근한 방법은 다음과 같습니다:

• 전역 변수가 많습니다. 초기 물고기들의 위치와 크기를 담은 2d array fish, 방문 여부를 기록할 2d array visited, 상어의 크기 shark, 최소거리 min_d와 이때의 좌표 minX, minY, 상어의 좌표 location 등등.
• 먼저, 입력을 받습니다. 이때 상어의 위치 (9)가 들어오면, 해당 위치의 값을 0으로 설정하고, 상어의 좌표를 기록합니다.
• loop를 통해 더 이상 먹을 물고기가 없을 때까지 다음을 반복합니다:
  • bfs를 통해 먹을 수 있는 물고기 중 가장 가까운 곳을 찾습니다. 상하좌우 탐색을 위해 moveX, moveY를 사용하고, boundary를 넘거나 이미 방문한 경우, 혹은 물고기의 크기가 상어의 크기보다 큰 경우 탐색할 수 없으므로 continue 합니다.
  • 새 위치를 방문했음으로 마킹합니다.
  • 물고기가 있고, 상어의 크기보다 작을 경우, minX, minY 좌표를 갱신합니다. 먹을 수 있는 물고기가 여럿 있을 경우, 위에 있는 물고기를 우선하고, 가장 위에 먹을 수 있는 물고기가 두 마리 이상 있을 경우, 가장 왼쪽에 있는 물고기를 먹도록 합니다.
  • 탐색을 마치면 해당 위치를 enqueue 합니다.
• 위 과정을 상어의 좌표를 갱신하며 반복하면 됩니다. 더 이상 탐색할 곳이 없는 경우 위의 loop를 break합니다.

문제의 세세한 조건들 때문에 코드가 좀 길어진 감이 있네요.