피크닉
-
[알고리즘] 알고스팟 소풍 PICNIC프로그래밍/알고리즘 2019. 3. 22. 15:24
알고스팟 소풍 PICNIC 문제 바로가기 백트래킹으로 문제를 해결하였다. 보통 이런식으로 모든 방법의 수를 구하는 방법은 백트래킹으로 구하는 경우가 많은 것 같다. 이와 반대로 가장 먼저 도달하는 방법을 구하는 경우는 BFS가 많은 것 같은데... 이것도 더 익숙해져서 문제를 바로바로 어떤식으로 풀지 머릿 속에 나올 정도가 됐으면 좋겠다.... 먼저 친구관계를 저장해줄 friends 라는 이차원 boolean배열을 만들어서 친구관계를 저장하였고, 짝이 정해졌는 지 확인해줄 visited라는 boolean 배열도 만들어 주었다. 이 후 재귀함수를 만들어서 아직 짝이 없는 친구들을 짝을 주어지는 식으로 백트래킹을 해줬다. 구현 코드는 아래와 같다. /** * https://algospot.com/judge/..