제출 코드
- 사용 알고리즘 :
BFS
최단거리 문제니까 BFS 풀어서 해결했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.*;
class Solution {
class Node{
int i, j;
Node(int i, int j){
this.i = i;
this.j = j;
}
}
public int solution(int[][] maps) {
int answer = 1;
int N = maps.length;
int M = maps[0].length;
int[] di = {-1, 0, 1, 0};
int[] dj = {0, 1, 0, -1};
Queue<Node> queue = new LinkedList<Node>();
queue.add(new Node(0, 0));
maps[0][0] = -1;
while(!queue.isEmpty()){
answer++;
int size = queue.size();
for(int s=0; s<size; s++){
Node now = queue.poll();
for(int d=0; d<4; d++){
int ni = now.i + di[d];
int nj = now.j + dj[d];
if(ni==N-1 && nj==M-1) return answer;
else if(ni<0 || ni>=N || nj<0 || nj>=M || maps[ni][nj]==-1 || maps[ni][nj]==0) continue;
queue.add(new Node(ni, nj));
maps[ni][nj] = -1;
}
}
}
return -1;
}
}