백준 21772 자바 - 가희의 고구마 먹방 (BOJ 21772 JAVA)

https://www.acmicpc.net/problem/21772

 

  BFS로 착각할 여지가 있는 문제이다. 하지만 한번 지나간 곳을 다시 올 수 있다는 점과, 지나간 경로상에 있는 고구마의 갯수를 세야 하는 문제이므로 방문체크를 할 수 없다. 따라서 모든 경로를 보는 Brute Force 문제이다. 정확히 따지자면 내 로직의 경우 사실 모든 경우를 보진 않았고, 답이 될 수 없는 경로인 경우 취소시켰으므로 Back Tracking이라 봐도 되는데, 어차피 모든경로 다 봐도 시간초과가 나진 않으므로 큰 의미는 없다.

 

  t가 최대 10이고 한 장소에서 상하좌우 4개의 방향으로 이동 가능하므로 최대 O(4^10) 짜리 BF라고 보면 된다.

그냥 DFS 돌리면서 모든 경우를 확인하면 된다. 주의점은 '가희가 고구마를 먹으면, 고구마가 다시 그 자리에 생기지 않습니다.' 라는 지문 부분이다. 이걸 따로 처리하지 않을 경우 다음과 같은 문제가 생긴다.

3 3 10
#S#
SGS
#S#

위와 같은 입력에서 고구마가 총 4개이니 답은 4가 나와야하는데, 어쨌든 고구마 있던 위치로 다시 가버릴 수 있으니 5라는 답이 나오게 된다.

 

  그렇다고 무작정 이미 먹었다고 고구마를 제거해버리면, 다른 경로를 통해 도착한 평행세계(?)의 가희가 고구마를 먹을 수 없게된다. 따라서 현재 지점에서 고구마를 먹은 경우, dfs에서 이전 지점으로 다시 되돌아갈 때 다시 고구마를 생성시켜놔야한다! (코드에서 19~24line에서 현재가 고구마라면 제거한 후, return되서 다시 이전 지점으로 되돌어가기 전인 36~38line에서 고구마를 제거했다면 다시 고구마를 생성되도록 했다.)

 

  그 외에 코드에서 16~17line 부분은 남아있는 t에 대해 현재까지 나온 답보다 현재 경로에서 가능한 최대치 (cnt+t+1)가 더 낮다면 해당 경로로는 더이상 진행하지 않도록 한 부분이다. 이 부분을 추가함으로 현재로썬 백준에서 자바 코드 중 가장 빨라졌다. :) 26~28 line은 일반적으로 DX, DY 처럼 배열로 (-1,0), (1,0), (0,-1), (0,1) 쌍이 되도록 해두고 다음 경로 찾아가는 그거임. 그냥 배열 만들기가 왠지 싫어서 저렇게 했다. 의외로 배열보다 아주아주살짝 빠르긴한데(어차피 배열도 위치 찾아가려고 덧셈, 곱셈 연산 들어가서..) 유의미한 속도는 아니라 큰 의미가 있는 코드는 아니다.

 

https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/21700/BOJ_21772.java