백준 1103번(JAVA)
이 문제는 DFS와 다이나믹프로그래밍을 모두 적용시켜야 하는 문제이다. DFS를 진행하는도중 만약 방문된곳을 한번 더 방문했다면 바로 -1을 출력하고 프로그램을 종료시켰다 왜?? 경로에 사이클이 생성되었다는 뜻이기 때문이다. DP배열은 단순히 해당 지점까지의 게임횟수를 의미한다. 그런데 만약 다음지점에서의 dp값이 10이다. 근데 현재 지점에서까지의 게임횟수는 5이면 다음지점으로 넘어갈 필요가 있는가? 답은 X다. 왜냐하면 우리는 최대게임횟수를 찾는것이기 때문이다. 위의 내용을 머리에 넣고 아래 소스코드를 보면 이해가 갈것이다. 소스코드 import java.io.*; import java.util.*; public class Main { public static int N; public static i..
