프로그래머스 알고리즘/Java
[프로그래머스] 게임 맵 최단거리 - Java
리버🐦🔥
2025. 4. 25. 00:59
https://school.programmers.co.kr/learn/courses/30/lessons/1844
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
⭐️ 중요 포인트
1. 제한 조건(벽, (n, m)이 목표)을 잘 따르고
2. isVisited[][]로 기존에 방문한 곳을 방문하지 않으며
3. BFS를 돌면 간단하게 해결할 수 있는 문제.
import java.util.*;
class Solution {
static class Pos {
int x;
int y;
int cnt;
Pos(int x, int y, int cnt) {
this.x = x;
this.y = y;
this.cnt = cnt;
}
}
static int[] dx = {0, 1, 0, -1};
static int[] dy = {-1, 0, 1, 0};
static int[][] sMaps;
static boolean[][] isVisited;
static int answer;
static void init(int[][] maps) {
sMaps = maps;
isVisited = new boolean[sMaps.length][sMaps[0].length];
answer = 0;
}
static boolean isInRange(int x, int y) {
if (0 <= y && y < sMaps.length && 0 <= x && x < sMaps[0].length ) {
return true;
}
return false;
}
static int bfs() {
Deque<Pos> q = new ArrayDeque<>();
q.add(new Pos(0, 0, 1));
isVisited[0][0] = true;
while (!q.isEmpty()) {
Pos curPos = q.pop();
int curX = curPos.x;
int curY = curPos.y;
int curCnt = curPos.cnt;
if (curY == sMaps.length - 1 && curX == sMaps[0].length - 1) {
return curCnt;
}
for (int i = 0; i < 4; i++) {
int nextX = curX + dx[i];
int nextY = curY + dy[i];
if (isInRange(nextX, nextY) && sMaps[nextY][nextX] == 1 && !isVisited[nextY][nextX]) {
q.add(new Pos(nextX, nextY, curCnt + 1));
isVisited[nextY][nextX] = true;
}
}
}
return -1;
}
public int solution(int[][] maps) {
init(maps);
answer = bfs();
return answer;
}
}