(JAVA) 백준 1103번 : 게임 --- [DFS, DP]

www.acmicpc.net/problem/1103

1103번: 게임

 

안녕하세요.

 

처음에 경로의 최대 개수를 구하는 줄 알고 풀었다가

 

문제를 다시 보니

 

 

밑줄 친 부분과 같이 종료 지점이 따로 존재하는 게 아니라 H(구멍)에 도착하거나, 맵 밖으로 벗어나면 종료하는 것이기 때문에

 

별도의 경로가 존재하지 않다는걸 깨달았습니다.

 

즉, 매 지점마다 4방향으로 튈 수 있다는 뜻이므로 최대 4^(50*50) 의 경우의 수가 존재하고, 이는 곧 시간 초과를 불러옵니다.

 

 

따라서, DP 를 활용해서 해당 지점까지 도달하는 게임 횟수를 저장해둔 다음, 현재 진행중인 게임 횟수와 DP 값을 비교하여 중복 진행을 줄입니다.

 

 

다음, 사이클이 생기면 무조건 -1을 출력해야 합니다. 사이클이란, 게임 진행 중에 이전에 도착한 지점에 다시 도착한 경우를 뜻합니다.

이러한 사이클을 찾기 위해 무던히 애썼습니다..ㅠㅠ

 

백트래킹 방식을 활용해서 별도 visited boolean 배열을 만들어 방문 여부를 체크하며, DFS 함수 재귀 호출 전 해당 지점 방문 여부를 True로 변경, 함수 호출 종료 후 다음 코드줄에는 해당 지점 방문 여부를 False로 변경합니다.

 

이를 통해 현재 DFS 를 통해 진행중인 경로 체크를 할 수 있고, 이는 곧 사이클 체크까지 가능하게 되었습니다.

 

 

마지막으로, H(구멍)에 도달하거나, 맵 밖을 벗어나면 종료하는데 이 때 게임 1번 더 해서 나온 결과이므로 현재까지 진행한 게임 횟수 + 1 번이 정답입니다. 저도 이것때문에 한참 해맸습니다...

 

*** 체크를 위한 테스트케이스

1.

input

6 7

12HHHHH

2214HHH

H1HHHHH

H4H9H2H

HHHHHHH

HHH2HHH

 

output

7

 

2.

input

5 5
4HHH9
HHHHH
HHH12
HHHHH
3HH2H

 

output

6

 

 

위 세 가지만 주의해서 문제를 푸신다면, 쉽게 해결하실 수 있습니다.

단순한 DFS + DP 알고리즘 활용이니까요!

 

아래 소스코드 첨부하겠습니다.

 

이상입니다.

 

감사합니다!

 

 

 

소스코드

---