[백준] 내리막 길

[hye-on]

🔗 내리막 길

[hye-on]

📑 댓글 템플릿

• Language : C++
• 성능

코드 풀이

```cpp #include #include #include #include //:3:37 ~ 4:05 using namespace std; int N,M; int graph[500][500]; int answer; int cnt[500][500]; bool OOB(int Y,int X){ if(Y>=M || Y<0 || X>=N || X<0) return false; return true; } void bfs(){ priority_queue>>q; // 이전 node값, y,x좌표 //높은애들 먼저 q.push({graph[0][0],{0,0}}); int dx[] ={0,1,0,-1}; int dy[] = {1,0,-1,0}; cnt[0][0]=1; while(!q.empty()){ int curY = q.top().second.first; int curX = q.top().second.second; int lastN = q.top().first; q.pop(); // if(curY==M-1 && curX==N-1){ // continue; // } for(int i=0;i<4;i++){ int ny = curY + dy[i]; int nx = curX + dx[i]; if(!OOB(ny,nx)) continue; if(graph[ny][nx]>M>>N;//세로 가로 for(int i=0;i>graph[i][j]; } } bfs(); cout<

코멘트

- 카카오 풀다가 백준푸니까 체감상 쉬웠던것 같습니다 😭

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

```java import java.io.*; import java.util.*; /** * 19:10 시작! 19:49 끝! (40분) */ public class Main { /** * 모든 경로의 수? dfs! O(MN) ~= 250,000 but 시간 초과가 남.. * 왜냐하면 최단거리로 가는 것이 아니기 때문에 방문한 곳을 또 가도됨! * 따라서, dp로 이미 방문한 곳은 중복 연산을 하지 않는 것이 중요! * 💡 어떤 지점은 애초에 가는 방법이 0일수도 있기 때문에 dp를 0이아닌 값(ex. -1)로 초기화 해야 함! */ static int[] dx = {-1, 0, 1, 0}; static int[] dy = {0, 1, 0, -1}; static int N, M; static int[][] map, dp; public static void main(String[] args) throws Exception { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(bf.readLine()); M = Integer.parseInt(st.nextToken()); // 세로 길이 N = Integer.parseInt(st.nextToken()); // 가로 길이 map = new int[M][N]; for(int i = 0; i < M; ++i) { st = new StringTokenizer(bf.readLine()); for(int j = 0; j < N; ++j) { map[i][j] = Integer.parseInt(st.nextToken()); } } // (0, 0)에서 (M-1, N-1)까지 갈 수 있는 경우의 수 (항상 내려가도록) dp = new int[M][N]; for(int i = 0; i < M; ++i) Arrays.fill(dp[i], -1); System.out.println(dfs(0, 0)); } public static int dfs(int x, int y) { if(dp[x][y] != -1) return dp[x][y]; if(x == M -1 && y == N - 1) return 1; int total = 0; for(int d = 0; d < 4; ++d) { int nx = x + dx[d]; int ny = y + dy[d]; if(nx >= 0 && nx < M && ny >= 0 && ny < N && map[nx][ny] < map[x][y]) { total += dfs(nx, ny); } } return dp[x][y] = total; } } ```

코멘트

- 처음엔 dfs를 생각했는데, 최단거리로 가는 것이 아니기 때문에 방문했던 곳을 또 방문할 수 있더라구요! 그렇게 되면 탐색 범위가 너무 넓어서 일반적인 dfs로는 시간초과가 나고 dp를 통해 최적화를 해야 하는 문제였습니다!