Java 알고리즘 - 두개 코드의 차이점 아시는분 있나요..?

Question

BFS 알고리즘을 이용해 푼 문제가 있습니다.근데 제가 생각할땐 결국 같은 코드인데 하나는 시간초과, 하나는 통과하더라구요..코드를 요약하자면... 두개의 코드는 아래와 같습니다.(참고로 아래 코드에서 init 함수는 큐에 초기값을 넣어주기위해 인덱스를 찾는 과정입니다.) 첫번째코드(시간초과)while(true){ int[] idx &#61; init(); if(idx[0]&#61;&#61;0 && idx[1]&#61;&#61;0) break; if(BFS(idx[0],idx[1])) break; } public static int[] init(){ int[] idx &#61; new int[2]; for(int i&#61;1; i<n-1; i&#43;&#43;){ for(int j&#61;1; j<m-1; j&#43;&#43;){ if(arr[i][j]!&#61;0) { idx[0]&#61;i; idx[1]&#61;j; return idx; } } } return idx; } public static boolean BFS(int xidx, int yidx){ //BFS 연산(연산중 조건문에 return true 있음) return false; } 두번째 코드(통과)while(true){ if(BFS()) break; } public static boolean BFS(){ int[] idx &#61; new int[2]; for(int i&#61;1; i<n-1; i&#43;&#43;){ for(int j&#61;1; j<m-1; j&#43;&#43;){ if(arr[i][j]!&#61;0) { idx[0]&#61;i; idx[1]&#61;j; break; } if(idx[0]!&#61;0 && idx[1]!&#61;0) break; } } if(idx[0]&#61;&#61;0 && idx[1]&#61;&#61;0) return true; //BFS 연산(연산중 조건문에 return true 있음) return false; } 제가 생각할때 두개의 코드는 결국 연산수는 똑같다고 생각이 드는데 차이점이 뭔지 알수 있을까요?고수님들 부탁드립니다ㅠㅠ

엡실론 · Answer

BFS 부분은 생략된거 같은데, 동일하다고 가정하면 init 부분만 다르네요.아래쪽 코드에서 14번, 15번째 줄이 바뀌어야 윗 코드와 동일해 집니다.윗 코드는 첫번째 0이 아닌 arr[i][j]를 찾는데 아래쪽 코드는 마지막 i 중 첫번째 j를 찾게 됩니다. 빅오 수준에서는 똑같지만, 아마도 시작점이 달라져서 의도하지 않게 뭔가가 달라진 것 같은데, 전체 코드도 없고 무슨 문제인지 모르니 확실하진 않습니다.

DongGeon2 · Answer

엡실론 일단 문제가 뭔지 찾았고 해결도 했습니다. 그리고 전체코드를 올렸어야 했는데 사정이 있어서 전체코드를 올리지 못했어요ㅠㅠ 그럼에도 답변 해주신 점 감사합니다.

Java 알고리즘 - 두개 코드의 차이점 아시는분 있나요..?

2개의 답변

Q&A 목록