[BOJ] 아기 상어

[reasonyi]

문제 링크

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

풀이 사항

풀이 일자: 2024.00.00 풀이 시간: 00분 00초 채점 결과: 오답/시간 초과/런타임 에러/정답 예상 문제 유형: 구현/BFS/DFS/DP/자료구조/문자열 등 시간: 00 ms 메모리: 00 kb

풀이 방법

(풀이 접근 및 방법에 대한 설명 문제를 풀지 못했다면 어느 곳에서 어려움을 느꼈는지 적어주세요!!)

[reasonyi]

문제 링크

185

풀이 사항

풀이 일자: 2024.09.03 풀이 시간: 1시간 16분 채점 결과: 정답 예상 문제 유형: 구현/BFS 시간: 116 ms 메모리: 15,292 kb

풀이 방법

처음에 bfs 방향만 상-좌-우-하 로 하면 될 줄 알고 그렇게 설정했으나, 문제의 같은 거리인 경우 먹는 순서 조건에 어긋나 오답.

• 물고기의 위치를 저장할 Point객체는 cnt, r, c순서대로 오름차순 정렬되도록 한다.
• 상어의 위치에서 bfs를 시작하여, 상어보다 크기가 작은 물고기를 처음 찾은 경우, max를 해당 거리만큼으로 설정하고, 같은 거리에 있으면서 먹을 수 있는 물고기를 모두 찾아 pq에 저장한다.
• pq가 비어있지 않은 경우, 첫 번째 물고기를 가져와 먹고, 변경해야 하는 값들을 조정한다.
• 만약 아무 물고기도 먹지 못한 경우, 종료.

[sangholee235]

문제 링크

175

풀이 사항

풀이 일자: 2024.09.02 풀이 시간: 32분 12초 채점 결과: 정답 예상 문제 유형: BFS 시간: 152 ms 메모리: 21,628 kb

풀이 방법

1. BFS로 단순 탐색
2. 먹을 수 있는 물고기를 발견했을때,
3. 현재 닿을 수 있는 물고기 중에 최소 인지 체크
4. 최소가 맞다면 더 위에있는지, 그렇지 않다면 가장 왼쪽 타겟팅
5. 먹을게 없는 순간까지 (BFS가 target을 못뱉으면) while문 종료
6. 그 순간에 카운팅된 time 리턴

[haesoooo]

문제 링크

200 🤗

풀이 사항

풀이 일자: 2024.09.04 풀이 시간: 2시간 채점 결과: 정답 예상 문제 유형: BFS, 구현 시간: 184 ms 메모리: 23,340 kb

풀이 방법

while (true) {

1. bfs로 상어보다 작거나 같은 값을 가진 칸에 대해 bfs()로 거리를 모두 구하기
2. 이중 for문에서 각 cell마다 상어보다 작은 값을 가진 칸에 대해 제일 가까운 애 구하기 (좌표, 거리 모두 갱신하면서)
3. 2번에서, 최소 거리 갱신이 이루어지지 않고, 나보다 작은 먹이가 없으면 while 문 탈출

4. 가장 가까운 애 먹기 (가까운 먹이와의 거리만큼 시간 증가, 좌표를 그 먹이 위치로 이동, 그 먹이 위치는 cell 값 0으로)

   }

상어가 존재하던 cell을 처음에 0으로 초기화 해줘야 한다. 몸집이 같은 먹이를 먹지는 못하지만 지나갈 수는 있다!!

[chanu2]

문제 링크

203

풀이 사항

풀이 일자: 2024.09.03 풀이 시간: 1시간 50분 채점 결과: 정답 예상 문제 유형: BFS, 구현 시간: 156 ms 메모리: 22400 kb

풀이 방법

• while을 돌면서
• bfs로 상어보다 작거나 같은 값을 가진 칸에 대해 bfs()로 거리를 모두 구하기
• 방문한 곳의 크기가 가장 가깝고 물고기가 존재한다면 x 값을 기준으로 최솟값을 갱신한다, 만약에 x값이 같다면 y값의 최솟값 갱신
• 상어의 크기를 바꿔준다.
• 만약에 최솟값이 갱신되지 않고 그대로이면 종료(갈 곳이 없어서)