uijin-j
commented
4 days ago 📑 댓글 템플릿
- Language : Java
- 성능
풀이 1
풀이 2
코드 풀이
풀이 1 (그리디)
```java import java.util.*; // 17:06 START! 18:48 END! (풀이 참고..) class Solution { /** * 그래프 탐색 (bfs) * - 일반적인 bfs와 다른 점: 또 방문할 수 있음 / 최단거리가 아닌 일정 거리 k로 가는 방법을 구해야 함 * 깊이가 k로 정해져 있으니까 dfs가 더 나을 것 같다! => 중복 방문이 허용되기 때문에 O(4^k).. 시초ㅜㅜ * * 최단거리를 구한 뒤 상쇄하는 방식은 어떨까? 근데 최단거리를 구한 뒤 상쇄한 방식이 돌아가는 것보다 사전순으로 빠르다고 할 수 있을까? * ❗️ 애초에 S, E를 알고 있으니, 최단거리는 알고 있는거나 다름 없음! * * 💡 그리디처럼 사전순으로 빠른 방향으로 갈 수 있으면, 그 방향으로 가자! */ public String solution(int n, int m, int x, int y, int r, int c, int k) { String answer = ""; // S에서 E로 가기 위해 최소로 가야하는 방향 수 int down = Math.max(r - x, 0); int left = Math.max(y - c, 0); int up = Math.max(x - r, 0); int right = Math.max(c - y, 0); if(k < down + left + up + right) return "impossible"; if((k - (down + left + up + right)) % 2 == 1) return "impossible"; // 상쇄하려면 2개씩 짝을 지어야 함 int pair = (k - (down + left + up + right)) / 2; for(int i = 0; i < k; ++i) { // k번 움직이기 // 아래로 갈 수 있다면, 아래로 가는 것이 이득! if(x < n && (down > 0 || pair > 0)) { answer += "d"; x += 1; if(down > 0) { down--; } else { pair--; up += 1; } continue; } // 왼쪽으로 갈 수 있다면, 왼쪽으로 가는 것이 이득! if(y > 1 && (left > 0 || pair > 0)) { answer += "l"; y -= 1; if(left > 0) { left--; } else { pair--; right += 1; } continue; } // 오른쪽으로 갈 수 있다면, 오른쪽으로 가는 것이 이득! if(y < m && (right > 0 || pair > 0)) { answer += "r"; y += 1; if(right > 0) { right--; } else { pair--; left += 1; } continue; } // 위로 갈 수 있다면, 위로 가는 것이 이득! if(x > 1 && (up > 0 || pair > 0)) { answer += "u"; x -= 1; if(up > 0) { up--; } else { pair--; down += 1; } continue; } } return answer; } } ```풀이 1 (DFS)
```java import java.util.*; // 17:06 START! class Solution { /** * 그래프 탐색 (bfs) * - 일반적인 bfs와 다른 점: 또 방문할 수 있음 / 최단거리가 아닌 일정 거리 k로 가는 방법을 구해야 함 * 깊이가 k로 정해져 있으니까 dfs가 더 나을 것 같다! => 중복 방문이 허용되기 때문에 O(4^k).. */ String answer; boolean found; int[] target; int n, m, k, r, c; public String solution(int n, int m, int x, int y, int r, int c, int k) { answer = ""; target = new int[]{r-1, c-1}; this.n = n; this.m = m; this.k = k; int minDistance = Math.abs(x - r) + Math.abs(y - c); if(k < minDistance) return "impossible"; if((k - minDistance) % 2 == 1) return "impossible"; StringBuilder sb = new StringBuilder(); dfs(0, x-1, y-1, new StringBuilder()); return answer == "" ? "impossible" : answer; } String[] d = {"d", "l", "r", "u"}; int[] dx = {1, 0, 0, -1}; int[] dy = {0, -1, 1, 0}; public void dfs(int level, int x, int y, StringBuilder sb) { if(found) return; if(level == k) { if(x == target[0] && y == target[1]) { answer = sb.toString(); found = true; } return; } int minDistance = Math.abs(x - target[0]) + Math.abs(y - target[1]); if(k - level < minDistance) return; for(int i = 0; i < 4; ++i) { int nx = x + dx[i]; int ny = y + dy[i]; if(nx >= 0 && nx < n && ny >= 0 && ny < m) { sb.append(d[i]); dfs(level + 1, nx, ny, sb); sb.deleteCharAt(sb.length() - 1); } } } } ```코멘트
- 딱 문제가 dfs/bfs 문제 유형과 비슷해서 해당 방식을 고민했는데.. 최단거리를 구하는 문제 ❌ (이미 거리는 K로 고정), 재방문 ⭕️ 라는 점에서 그래프 문제가 아니라는 걸 캐치했어야 했네요큐ㅠ (시초 날 것 같았는데, 최적화하면 될 줄 알았숩니다..) - 이미 시작 지점과 목표 지점을 알고 있고, 중간에 장애물이 없다는 점에서 힌트를 얻어 최소 상/하/좌/우로 몇번 가야 도착하는 지를 파악한 뒤, impossible인 경우를 걸러내야 했습니다! (k가 최단 거리보다 짧을 때, 최단 거리에서 추가적으로 가야하는 거리가 2의 배수가 아닐 때)
- 이후 경로를 구할 때, 시작 지점부터 d → l → r → u 순서로 그리디하게 가면 되는 문제였습니다! (이전 문제가 그리디라 그리디는 아닐 줄 알았는데.. 속았습니다..🥲)
- 속은 줄 알았는데, 혜온님 풀이 보니까 dfs 문제가 맞네용🤣 시초가 안날려면, early return 할 수 있는지 고민을 해야될 것 같습니다! (이 문제에서는 남은 거리로 E에 도착할 수 없으면 탐색 중단! + 처음에 갈 수 없는 경우 구하기)
hye-on
🔗 미로 탈출 명령어