백준 알고리즘 풀이 도와주세염

Question

https://www.acmicpc.net/problem/11558문제 링크구요public class Main { public static void main(String[] args) throws IOException{ BufferedReader bf &#61; new BufferedReader(new InputStreamReader(System.in)); int T &#61; Integer.parseInt(bf.readLine()); // hh : 희현 , route : 담을 값 int hh &#61; Integer.parseInt(bf.readLine()); int[] route &#61; new int[hh&#43;1]; int point &#61; 1; int cnt &#61; 0; // 몇번 이동했는지 희현이를 지목시키려고 boolean self &#61; false; while(T-- > 0) { // 테스트 케이스 값 만큼 for(int i&#61;1; i<route.length; i&#43;&#43;) { route[i] &#61; Integer.parseInt(bf.readLine()); } for(int i&#61;1; i<hh-1; i&#43;&#43;) { if(point &#61;&#61; hh) { break; } point &#61; route[i]; cnt&#43;&#43;; self &#61; (route[i] &#61;&#61; 1) ? true : false ; } if(self &#61;&#61; true || cnt &#61;&#61; hh) { cnt &#61; 0; } System.out.println(cnt); } }}제 풀이인데 자기와 같은 값이 나오면 지목이 주경이에게 갈 수 없고, 다 돌았을 때도 값이 같으면 못만났다는 가정하에cnt &#61; 0으로 가게해서 정답을 나오게했는데 어느 부분이 잘 못된지 알 수 있을까요?

코딩하는나그네타는타조 · Answer

그냥 N 번에 연결된 숫자중에 제일 작은거 부르면 되는거아녜요?

제리콕 · Answer

우선 의도하신 바가 무엇인지는 알겠습니다. 입력 예제만 맞추기 위해 코드를 수정하자면for(int i=1; i<hh-1; i++) { ==> 이 부분에서 i반복을 i<=hh로 하면 출력 결과 6이 나옵니다.그러나 접근이 잘못되었습니다.반례로143421를 입력하면 답이 2가 나옵니다. 3이 나와야 맞습니다.1번인 희현이가 3번을 찍고3번이 2번을 찍고2번이 4번(주경)을 찍게 되어 3이 나와야합니다.즉, 위 문제는 dfs(깊이 우선 탐색) 문제이므로 재귀함수로 구현하셔야 합니다.

제리콕 · Answer

dfs 코드를 작성 하실 때, 방문 했던 번호에는 방문 표시를 하여싸이클이 발생하지 않도록 하셔야합니다.ex) 1번 -> 2번2번 -> 3번3번 -> 1번 ------- 1번은 이미 방문 했으므로 더이상 진행하면 스택오버플로우 에러가 발생됩니다.즉, 싸이클 없이 1번에서 N번 까지 몇 번의 dfs가 수행되는지 찾아주면 도착 플래그를 true로 주어서 종료시켜 주시면 될 것 같습니다.

백준 알고리즘 풀이 도와주세염

3개의 답변

기타 목록