역시 리트코드 하드 문제는 생각을 많이 하게 만든다. ldru 방향으로 최소 거리를 찾는 문제인데 예전에 카카오 코딩테스트 문제가 생각났다.
비슷한 결의 문제 같긴해서 다음에 시간 내서 풀어볼 예정이다. C++ 로도 똑같은 로직을 적용해서 풀어봤는데 내꺼는 잘 안되어서 결국 해답을 보고 제출 했다.
너무 많은 시간을 사용한거 같은데 그래도 전체적인 흐름을 적용해보면은 다익스트라를 적용 해야한다.
하지만, 다익스트라의 커스텀 조건에 하나를 더 추가해야하는데 최소한의 거리 + 가장 빠른 알파벳 순서를 적용시켜서 Priority Queue 의 순서를 유지 해야했다.
PQ의 활용도가 객체랑 합쳐지면 꽤 높은거같아서 자주 사용하게 된다.
class State{
int row;
int col;
int dist;
String path;
public State(int row, int col, int dist, String path){
this.row = row;
this.col = col;
this.dist = dist;
this.path = path;
}
}
class Solution {
int[][] directions = new int[][]{{0,-1},{-1,0},{0,1},{1,0}};
String[] textDirections = new String[]{"l","u","r","d"};
int m;
int n;
public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
m = maze.length;
n = maze[0].length;
PriorityQueue<State> heap = new PriorityQueue<>((a,b) -> {
int distA = a.dist;
int distB = b.dist;
if(distA == distB){
return a.path.compareTo(b.path);
}
return distA - distB;
});
boolean[][] seen = new boolean[m][n];
heap.add(new State(ball[0], ball[1], 0, ""));
while(!heap.isEmpty()){
State curr = heap.remove();
int row = curr.row;
int col = curr.col;
if(seen[row][col]){
continue;
}
if(row == hole[0] && col == hole[1]){
return curr.path;
}
seen[row][col] = true;
for(State nextState: getNeighbors(row, col, maze, hole)){
int nextRow = nextState.row;
int nextCol = nextState.col;
int nextDist = nextState.dist;
String nextChar = nextState.path;
heap.add(new State(nextRow, nextCol, curr.dist + nextDist, curr.path + nextChar));
}
}
return "impossible";
}
private boolean valid(int row, int col, int[][] maze){
if(row < 0 || row >= m || col < 0 || col >= n){
return false;
}
return maze[row][col] == 0;
}
private List<State> getNeighbors(int row, int col, int[][] maze, int[] hole){
List<State> neighbors = new ArrayList<>();
for(int i = 0; i < 4; i++){
int dy = directions[i][0];
int dx = directions[i][1];
String direction = textDirections[i];
int currRow = row;
int currCol = col;
int dist = 0;
while(valid(currRow + dy, currCol + dx, maze)){
currRow += dy;
currCol += dx;
dist++;
if(currRow == hole[0] && currCol == hole[1]){
break;
}
}
neighbors.add(new State(currRow, currCol, dist, direction));
}
return neighbors;
}
}