zo13258   2년 전

알고리즘을 풀면서 다른분에게 여쭤본다는 것이 큰 실례이고 귀찮은 점이라는 것을 알고 있습니다.

그래서 질문을 드리기 전에 죄송하다는 말씀을 먼저 드리고 시작하겠습니다.

제 질문은 다음과 같습니다.

아기상어 예제에서 4번 예제가 왜 60이 나오는지

전혀 이해가 되지 않습니다.

실제로 프로그램을 돌려봐도, 직접 손으로 풀어도 56이 나오는데

제가 어느 부분에서 잘못 이해를 한 것인지 코드를 통해 여쭤보고 싶습니다.

문제를 bfs로 풀었고, 탐색 순서는 상좌우하입니다.

소스코드를 첨부하오니 확인 부탁드리겠습니다. 감사합니다.

jh05013   2년 전

예제 4에서 물고기를 먹는 순서는 다음과 같이 나옵니다.

zo13258   2년 전

답변 감사드립니다.

제가 짠 코드로 돌려보니 이렇게 나옵니다.

입력 :

6

5 4 3 2 3 4

4 3 2 3 4 5

3 2 9 5 6 6

2 1 2 3 4 5

3 2 1 6 5 4

6 6 6 6 6 6

순서 :

35 11 6 5 12 13

10 7 4 15 14 33

9 8 0 16 34 32

28 1 3 17 18 19

27 26 2 22 21 20

29 25 24 23 30 31

맨 처음 순서가 바뀌는 구간은 6에서 7으로 넘어가는 구간이었습니다.

제 부족함을 알게 되었습니다. 감사합니다.

sotter1020   2년 전

저 혹시 이거 해결 하셨나요?

저도 똑같이 풀어서 문제점을 발견했는데..

어떻게 해결해야 할지 감이 안잡히네요 ㅠㅠ

아니면 다시 짜셨나요? 거기서 bfs에서 예외처리 해주셨나요?

lonecitizen   1년 전

@sotter1020

한달 전이라 이걸 읽으실지는 모르겠지만, BFS에서 방향벡터 쓰셔서 하는 경우에는 발견 즉시 물고기를 먹지 않게 하면 해결됩니다.

우선 먹을 수 있는 물고기의 위치를 표현하는 배열하나를 만드시고, 전체 탐색을 하셔서 해당 배열을 채워줍니다.

그다음에 for문 2개 row col순으로 돌려서 가장 먼저 발견되는 위치가 맨 위, 맨 왼쪽이므로 발견 즉시 먹고 count올리고 크기만큼 먹으면 크기 키워주고 등등 하시면 됩니다.

댓글을 작성하려면 로그인해야 합니다.