Programming/알고리즘
![[백준] 1520. 내리막 길 자바(Java) 풀이](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fbkp5Oj%2Fbtrfp23mDG5%2FxS1iO7OeuoQlZu4wPI23Pk%2Fimg.png)
[백준] 1520. 내리막 길 자바(Java) 풀이
1. 접근 방법 M과 N이 최대 500까지이기에 완전탐색을 할 경우 시간초과가 납니다. 그래서 DP를 이용해 이미 방문한 지점의 경우 다시 방문하지 않도록 중복을 제거해야만 합니다. 이차원 배열 dp[][]를 만듭니다. 그리고 dp에 해당 지점에 도달할 수 있는 경우의 수를 누적해서 저장해야 합니다. 예제를 보면 빨간 박스친 지점에서 중복이 발생합니다. 20 지점의 경우 2가지 방법으로, 15 지점의 경우 총 3가지 방법으로 도착할 수 있습니다. 단순히 BFS로만 풀게되면 아직 방문하지 않은 지점을 큐에 담을 때 20 지점이 담긴 후 32 > 30 > 25 > 20 의 경우의 수를 갱신하기 전에 먼저 큐를 빠져나가게 됩니다. 20에 도달할 수 있는 모든 경우의 수가 dp에 담은 후에야 20인 지점이 큐를..
[SWEA] 1249. 보급로 자바(Java) 풀이
1. 문제 접근방법 dfs, bfs로 풀 수 있는 문제입니다. 그러나 완전탐색으로 모든 지점을 방문하면 시간초과가 발생합니다. 그렇기에 조건에 부합하지 않는 경우의 수를 가지치기 해야만 합니다. 2. 문제풀이 1. 각 좌표의 깊이를 2차원 배열인 supply에 담는다. 2. 2차원 배열인 map을 만든 뒤, -1로 초기화한다. 3. supply 배열을 (0, 0) 에서 시작하여 bfs를 한다. 대신 조건에 맞는 경우에만 큐에 담는다. 3-1) 다음 가려고 하는 지점이 한번도 방문하지 않았을 경우 큐에 담는다. (if (map[nx][ny] == -1)) 3-2) 다음 가려고 하는 지점이 이미 방문했으나 그동안 지나온 깊이의 합보다 클 경우 방문한다. else if (map[nx][ny] > cur.sum..