사이클 판정2 [자바] 백준 1103 - 게임 (java) 목차 문제 : boj1103 필요 알고리즘 깊이 우선 탐색, DP, 사이클 판정 memoization을 통해 연산 횟수를 줄이면서 DFS를 진행하는 문제이다. 또한 사이클 판정하는 방법도 알아야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 사실 로직을 말로 하면 간단하다. 1. 가장 왼쪽 위부터 DFS를 진행한다. 2. 사이클이 한번이라도 생기는 경우 -1을 출력하고 끝낸다. 3. 사이클 없이 가장 멀리 간 거리를 .. 2023. 7. 26. [자바] 백준 1115 - 순열 (boj java) 문제 : boj1115 오랜만에 엄청 잘만들었다고 느낀 문제였다. 아이디어 문제이다. 해설은 간단한데, 사실 이걸 떠올리는게 전부인 문제이다. 1. B[0] = 0 이므로 즉 A[0]부터 시작한다고 보면 된다. 2. B[i]=A[B[i-1]] 은 즉 A[0]부터 시작한댔으니, A[0] -> A[A[0]] -> A[A[A[0]]] 이런식으로 진행하겠다는 의미이다. 이 때 이게 순열이 되려면 결국 중간에 끊기지 않고 모든 A원소들을 들릴 수 있어야 한다. 그럼 당연히 처음 입력된 A가 모두 들릴 수 있다면? 그냥 0으로 끝이다. 중요한건 중간에 끊길 경우, 어떻게 최소로 교환해서 전체를 들릴 수 있도록 만들 것인지가 관건이다. 직관적으로 이걸 그래프로 생각해보면 좀 더 생각하기 편한데, 결국 끊겼다는 것은 .. 2022. 5. 17. 이전 1 다음
