<Algorithm> 201. 게임맵최단거리(Programmers)
by BFine반응형
1. 게임맵최단거리(Programmers)
사용 알고리즘 : BFS
기본적인 경로의 최소값 문제 solve를 호출해야 하는데 solution을 호출해 StackOverFlow가 발생했었다....
당연히 잘못썼다는 생각을 못하고 로직의 문제점만 찾다가 출력이 아예 안되는 것을 발견한 후에야 알았다...
문제에 대한 접근&생각
- 왼쪽 끝에서 오른쪽 끝까지 가는 경로 최솟값 -> 결과조건!
- 이 경로는 여러가지가 있을 수 있음 -> 경로수가 아닌 최단경로 비용 필요 -> DFS! or 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
59
60
61
|
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
static int[] dx = {0,0,1,-1};
static int[] dy = {1,-1,0,0};
static int n;
static int m;
public int solution(int[][] maps) {
int answer = 0;
n = maps.length;
m = maps[0].length;
/******************************
* BFS 탐색을 통해서 끝점까지가는
* 경로의 최솟값을 구한다.
*******************************/
visited = new boolean[n][m];
dist = new int[n][m];
answer = solve(maps);
return answer;
}
static boolean[][] visited;
static int[][] dist;
public int solve(int[][] maps) {
Queue<Pair> queue = new LinkedList<>();
queue.add(new Pair(0, 0));
visited[0][0] = true;
dist[0][0] = 1;
while (!queue.isEmpty()) {
Pair p = queue.remove();
for(int i = 0; i < 4; i++) {
int nx = p.x + dx[i];
int ny = p.y + dy[i];
if(isBoundary(nx, ny) && maps[nx][ny]==1) {
visited[nx][ny] = true;
dist[nx][ny] = dist[p.x][p.y]+1;
queue.add(new Pair(nx, ny));
if(nx == n-1 && ny == m-1) {
return dist[nx][ny];
}
}
}
}
return -1;
}
public boolean isBoundary(int nx, int ny) {
if(nx < 0||ny < 0||nx >= n||ny>=m||visited[nx][ny]) {
return false;
}else
return true;
}
static class Pair{
int x,y;
public Pair(int x, int y) {
super();
this.x = x;
this.y = y;
}
}
}
|
|
cs |
반응형
'공부(2018~2019) - 스킨변경전 > Algorithm' 카테고리의 다른 글
| <Algorithm> 203. 탑(BJO) (0) | 2019.05.21 |
|---|---|
| <Algorithm> 202. 하노이 탑 이동순서(BJO) (0) | 2019.05.20 |
| <Algorithm> 200. 설탕배달(BJO) (0) | 2019.05.07 |
| <Algorithm> 199. 이친수(BJO) (0) | 2019.05.05 |
| <Algorithm> 198. 오르막수(BJO) (0) | 2019.05.03 |
블로그의 정보
57개월 BackEnd
BFine