알고리즘/BFS|DFS
[프로그래머스 연습문제 level_2 ] 게임 맵 최단거리
happyhelen
2023. 11. 29. 14:48
import java.util.*;
class Solution {
static int[][] D = {{-1,0},{1,0},{0,-1},{0,1}};
static int N, M;
static class Point{
int row, col, dist;
Point(int r, int c, int d){
row = r; col = c; dist = d;
}
}
public int solution(int[][] maps) {
int answer = 0;
N = maps.length;
M = maps[0].length;
answer = bfs(maps, 0,0,N,M);
return answer;
}
static int bfs(int[][] maps, int sRow, int sCol, int eRow, int eCol){
boolean[][] visited = new boolean[eRow][eCol];
visited[sRow][sCol] = true;
Queue<Point> myQueue = new LinkedList<>();
myQueue.add(new Point(sRow, sCol, 1)); // 모든 칸의 개수를 세는 것이므로 1부터 시작
while(!myQueue.isEmpty()){
Point curr = myQueue.remove();
if(curr.row == eRow-1 && curr.col == eCol-1){ // 배열의 길이에서 -1 한 것이 위치값이므로
return curr.dist;
}
for(int i=0; i<4; i++){
int nr = curr.row + D[i][0], nc = curr.col + D[i][1];
if(nr < 0 || nr > N-1 || nc < 0 || nc > M-1) continue;
if(visited[nr][nc]) continue;
if(maps[nr][nc] == 0) continue;
visited[nr][nc] = true;
myQueue.add(new Point(nr, nc, curr.dist + 1));
}
}
return -1;
}
}