- Today
- Yesterday
- Total
메이쁘
(JAVA) 백준 1890번 : 점프 --- [DFS, DP] 본문
1890번: 점프
첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 ��
www.acmicpc.net
안녕하세요.
바로 풀자마자 작성하는 게 아니라, 한 일주일 지나서 작성하는거라 풀이 방법이 가물가물하네요..
핵심은 해당 지점에서 목적지까지 갈 수 있는 경로의 개수 를 구하는 것입니다.
맵에서 해당 지점의 숫자는 오른쪽 또는 아래쪽 으로 갈 수 있는 칸의 개수 입니다.
이를 활용해서 경로를 어떻게 구하나 고민하다가,
DFS 를 사용했습니다.
하지만, 이렇게 DFS만 사용한다면, 쉬운 문제였곘죠.
조건은 시간제한 1초, 메모리제한 128MB 입니다.
게다가, 최단 거리나 최소 개수를 구하는게 아니라 가능한 경로의 개수 를 구하는 것이기 때문에
이전에 구했던 경로와 중복되선 안됩니다.
어떻게 하면 이전 경로와 중복되지 않게 하지? 고민했고,
결국 DP를 활용해서 경로의 개수를 구했습니다.
이를 위해 2차원 int 배열을 만들고, 여기에는 해당 지점에서 목적지까지 도착할 수 있는 경로의 개수 를 넣었습니다.
초기값은 0이기 때문에, 해당 지점에서 도착지점까지 갈 수 있는지 없는지 판단을 할 수 있고(+ 처음 방문한 지점인지도)
이동할 수 있는 다음 지점에 값이 0이 아니면 이미 이전에 이 지점부터 목적지까는 경로를 구했기 때문에 경로의 중복을 방지할 수 있습니다.
그래서 0이 아니면 그대로 그 경로의 개수를 가져와서 더하면됩니다.
이러한 경우를 오른쪽, 아래쪽 두 가지 전부 따져서 해당 지점의 경로의 개수를 구해서 배열에 저장!
음.. 먼가 글로 풀어쓰려니까 어렵습니다...
하단 소스코드를 보시면 아 이게 이런 말이었구나... 하실 것 같습니다.
이상입니다!
감사합니다.
소스코드
'Algorithm > Baekjoon' 카테고리의 다른 글
| (JAVA) 백준 1446번 : 지름길 --- [다익스트라] (0) | 2020.10.16 |
|---|---|
| (JAVA) 백준 2565번 : 전깃줄 --- [DP, LIS] (0) | 2020.10.16 |
| (JAVA) 백준 5670번 : 휴대폰 자판 --- [트라이] (0) | 2020.10.09 |
| (JAVA) 백준 15559번 : 내 선물을 받아줘 --- [DFS] (2) | 2020.10.06 |
| (JAVA) 백준 5214번 : 환승 --- [BFS] (0) | 2020.10.05 |
