lswoo3021   2년 전

안녕하세요 .. ! 또 이렇게 질문을 드리네요 ㅠㅡㅠ 

이번 문제도 역시 .. TC는 맞는데 오답으로 나오네요 ..ㅠ

  1. 반례가 있다면 부탁드리겠습니다.
  2. 문제의 접근 방법을 잘 몰라서 이래저래 풀었는데... 방법이 맞나요 ? (혹시 더 간편한 방법이 있다면 레퍼런스좀 부탁드려도 될까요 !! )

-최단거리를 찾을 때 visit[][]배열 외에 최단거리를 저장하는 distp[][]를 두어

현재 노드의 거리(dist[x + dx][y + dy]) = 이전 노드의 거리(dist[x][y]) + 1 로 

모든 정점에 대해 최단거리 맵을 정리함.

-> 기출 문제중 bfs의 최단거리 문제는 처음보는 것 같네요... 일반적인 bfs에서

최단거리(또느 깊이, 레벨)을 파악하기 위해 약간의 변형이 필요한 문제.. 맞나요 ? 

보통은 ㅠㅡㅠdfs든 bfs든 모든경우의수를 돌린뒤 min이나 max를 통해 단순비교하여 최소값/최댓값을 

찾았는데요... 제가 너무 안일하게 생각했나봐요 ㅠ 

정답률이 50%가 넘는데 다들 ㅠㅡㅠ 대단하신거같아요! 

저는 bfs에서 거리를 기록하는 방법을 잘몰라서 헤맸는데 말이져 ㅠㅡㅠ

감사합니다! 

ychooni   2년 전

거리가 같은 먹이들에 대한 우선순위가 있는데, 처리 하신건가요??

lswoo3021   2년 전

@ychooni 네ㅠㅡㅠ 94라인부터 117번까지가 우선순위 처리부분입니다... 저도 그게 의심스러워서 

같은거리에 여러가지 놓고 테스트를 해봤는데 그 부분은 문제에서 주어진대로 잘 처리하고있었습니다 

ychooni   2년 전

반례 드릴게요.

6

1 2 1 1 1 1 

1 3 6 2 2 3 

1 2 5 2 2 3 

3 3 2 4 6 3 

0 0 0 0 0 6 

0 0 0 1 1 9


39 나와야 하는데, 37 나옵니다.

lswoo3021   2년 전

@ychooni 감사합니다!! 덕분에 문제점 찾아서 정답완료했네요 ㅠㅠ 

원인은 .. 큰 물고기들로 인해 닿을수 없는 칸의 거리가 0으로 되어있어 제대로 돌지 않았네요... 

그경우만 조건에 추가해주니 됐습니다 !! 감사합니다. 

아 그리고 혹시 ㅠㅡㅠ 님께서는 문제 어떻게 푸셨는지 말씀해주실수 있을까요 !? ㅠㅡㅠ 

저는 bfs 기초만 알면되는 줄 알았는데, 제가 푼 방법대로 하지 않으면 안되는 건가요 ?! 

ychooni   2년 전

저는 좀 무식하게 풀어서 시간이 오래걸렸네요. 

일달 먹을 수 있는 고기들 찾아서 저장해 놓고, 각각의 거리를 구한다음 정렬을 했어요.(거리에 따른 우선순위는 정렬 기준으로 처리)

그리고 가장 먼저 먹어야 하는 고기의 거리의 누적시키고, 현재 상어의 위치를 갱신하는 방식.

그리고 반복. N 제한이 워낙 작아서 시도했던 방법이긴 한데...

4ms 나오신거 보니깐, 저보다 훨씬 효율적으로 짜신거 같아요. (사실 코드가 너무 길어서 제대로 보진 않았습니다..ㅜ)

"맞은 사람"에서 0ms 로 통과하신 분들의 코드를 분석해보는게 더 도움이 될거 같습니다. :)

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