dut0817   6년 전

처음에 벽에 있는 ㅏㅜㅓㅗ 모양 탐색했고

십자가 모양에서 min값 뺀 ㅗㅓㅏㅜ모양 탐색했고

그다음 나머지 모양들 탐색했어요 

시간초과가 자꾸 나요 ㅜㅜ 도와주세요 

rlaalswo01   6년 전

제가 자바를 잘 몰라서 그런데... 

  1. ㅗ 모양 빼면 깊이우선탐색으로 하시면 좋습니다.
  2. 도형의 시작점을 정해놓고 중복 탐색을 줄이면 좋습니다. 예를 들어 (1,2)에서 아래쪽으로 (4,2) 까지 막대기를 놓은것과 (4,2)에서 위쪽으로 (1,2) 까지 막대기를 놓은 것은 같습니다.

dut0817   6년 전

저는 bfs로 했는데요.. 비슷한거 아닌가요..?

rlaalswo01   6년 전

bfs도 가능할것 같은데, 이 코드에서 bfs가 있는지 몰랐네요.

저도 하수라 ㅎㅎ ; (제가 틀린 말을 하고 있다면 그냥 흘려주세요 ㅠㅠ)

117행 반복문이 bfs인가요?? 

제 생각엔 가장 큰 값을 찾아가는 것이 늘 최상의 조합을 보장하진 않을 것 같습니다.

남쪽이 북쪽보다 1 작아도 남쪽 좌표의 이웃들이 모두 북쪽 좌표의 이웃들보다 훨씬 큰 이웃들을 가지고 있을 수도 있지 않을까요?


86행부터 있는  ㅗ ㅓ ㅏ ㅜ  같은 경우, 자기값 + 4방의 원소값 - 갱신한 min값을 하면 굳이 인덱스를 저장하고 다시 참조해서 값을 빼는 등의 연산은 불필요할 것 같네요.

반복문 & 조건문들이 상당히 복잡해서 제가 다 분석하기에 한계가 있는데, 알고리즘의 문제가 아니라 조건문의 범위 등이 잘못되어서 무한루프를 돈다거나... 

저 같은 경우는 지금까지 그런 적도 많았습니다 ^^;

사실 반복문이 너무 많아지고 조건문이 너무 많아지면 디버깅이 어려워져요. 학생이신지 모르겠지만 학교에서 시험을 보거나 입사테스트등을 할때 이렇게 짜고 마음처럼 결과가 안나오면 시간내에 고치는 것은 불가능합니다. 재귀호출 등을 통해서 알고리즘을 간결화하면 어느 부분이 문제인지 잡아내시는데 도움이 됩니다.

dut0817   6년 전

그런데 무한루프를 도는 상황은 없지 않나요?? for문으로 범위를 다 지정해주었는데.. 그리고 답이 틀린게 아니라 시간 초과가 나서요 혹시 어느 부분에서 시간이 많이 소요될까 궁금했습니다..

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