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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| import java.util.LinkedList;
import java.util.Queue;
import java.awt.Point;
class Solution {
public static int solution(int[][] maps) {
int X = maps[0].length;
int Y = maps.length;
boolean[][] visited = new boolean[Y][X];
Queue<Point> q = new LinkedList<Point>();
int x = 0;
int y = 0;
int size = 0;
int cnt = 0;
Point p = new Point();
q.add(new Point(Y-1,X-1));
while(q.isEmpty()==false) {
size = q.size();
cnt++;
for(int i=0;i<size;i++)
{
p = q.peek();
x = p.y;
y = p.x;
q.remove();
if(visited[y][x]==true)
continue;
maps[y][x] = 0;
visited[y][x] = true;
if(x==0 && y==0) {
return cnt;
}
if(x-1>-1 && maps[y][x-1]==1) { //왼쪽 한칸
q.add(new Point(y,x-1));
}
if(x+1<X && maps[y][x+1]==1) { //오른쪽 한칸
q.add(new Point(y,x+1));
}
if(y-1>-1 && maps[y-1][x]==1) { //위쪽 한칸
q.add(new Point(y-1,x));
}
if(y+1<Y && maps[y+1][x]==1) { //아래쪽 한칸
q.add(new Point(y+1,x));
}
}
}
return -1;
}
}
|