프로그래머스 LV.2 게임 맵 최단거리
12877 단어 BFS프로그래머스 Lv.2알고리즘BFS
1. 문제 링크
2. 풀이
- 위치를 기록하는데 사용할 Pair 클래스를 선언했다.
- y 를 세로, x를 가로로 사용했다. - 방문 배열에는 이동 거리를 기록한다.
- BFS를 사용하여 최단 거리를 구한다.
3. 코드
import java.util.ArrayDeque;
import java.util.Queue;
public class Solution {
static class Pair {
int y, x;
public Pair(int y, int x) {
super();
this.y = y;
this.x = x;
}
}
static int[][] visit; // 방문한 경우 비용을 기록
static int[] dirY = {0, 0, 1, -1};
static int[] dirX = {1, -1, 0, 0};
public int solution(int[][] maps) {
int N = maps.length;
int M = maps[0].length;
visit = new int[N][M];
// BFS
Queue<Pair> q = new ArrayDeque<>();
// 시작점 큐에 삽임 & 방문 처리
q.add(new Pair(0, 0));
visit[0][0] = 1;
while (!q.isEmpty()) {
Pair now = q.poll();
for (int i = 0; i < 4; i++) {
int yy = now.y + dirY[i];
int xx = now.x + dirX[i];
if (yy < 0 || xx < 0 || yy >= N || xx >= M || visit[yy][xx] != 0 || maps[yy][xx] == 0)
continue;
// 다음 위치의 비용 = 현재 위치에 닿는 비용 + 1
visit[yy][xx] = visit[now.y][now.x] + 1;
q.add(new Pair(yy, xx));
}
}
int answer = -1;
// 도착했다면?
if (visit[N - 1][M - 1] != 0) {
answer = visit[N - 1][M - 1];
}
return answer;
}
}
4. 채점 결과
5. 느낀 점
- 기본적인 BFS 문제
Author And Source
이 문제에 관하여(프로그래머스 LV.2 게임 맵 최단거리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gan/프로그래머스-LV.2-게임-맵-최단거리저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)