게임 맵 최단 거리
문제 정보
- 사이트 : 프로그래머스 사이트
- 문제 번호 : 1844
- 문제 분류 : bfs
- 난이도 : level 2
문제 풀이
내가 짠 코드
생각한 문제 조건
1. n,m 크기의 map이 주어진다.
2. 0은 벽, 1은 이동 가능 한 칸이다.
3. 캐릭은 (0,0), 적은 (n-1,m-1)에 존재한다.
4. 이동은 상,하,좌,우로 가능하다.
5. 이동 횟수가 아닌 칸의 수를 출력해야한다.
6. 이동할 수 있는 경우 최소 이동 칸 수, 없는 경우 -1 출력한다.
💭 생각 노트
- 위치 값과 이동 칸 수를 담고 있는 Node Class 생성
- 최소 이동을 구해야 하므로 bfs를 사용한다.
- 기본 bfs 형태로 구현하면 될 것 같았다.
public class 게임_맵_최단거리 {
static Queue<Node> q = new LinkedList<>();
static int[][] check = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
static int n, m;
static boolean[][] visit;
static class Node {
int x;
int y;
int count;
public Node(int x, int y, int count) {
this.x = x;
this.y = y;
this.count = count;
}
}
public static int bfs(int[][] map){
while(!q.isEmpty()){
Node node = q.poll();
// 적을 만나면 이동 칸 수 출력
if(node.x == n-1 && node.y == m-1){
return node.count;
}
for (int i = 0; i < 4; i++) {
int dx = node.x + check[i][0];
int dy = node.y + check[i][1];
// 범위 안이고
if(0 <= dx && dx < n && 0 <= dy && dy < m){
// 방문 한적없는 이동 가능한 공간이면 queue에 추가
if(!visit[dx][dy] && map[dx][dy] == 1) {
visit[dx][dy] = true;
q.add(new Node(dx,dy,node.count+1));
}
}
}
}
return -1;
}
public static int solution(int[][] maps) {
n = maps.length;
m = maps[0].length;
visit = new boolean[n][m];
q.add(new Node(0,0,1));
visit[0][0] = true;
return bfs(maps);
}
public static void main(String[] args) {
int[][] maps = {{1,0,1,1,1},{1,0,1,0,1},{1,0,1,1,1},{1,1,1,0,1},{0,0,0,0,1}};
System.out.println(solution(maps));
}
}참고할만한 다른 코드
방문 check를 큐에서 넣을 때 해야하는 이유
만약 큐에 넣을 때가 아닌 꺼낼 때 방문 체크를 하게 되면 아래의 경우 이미 탐색한 곳을 또 큐에 넣을 수 있다.
아래는 처음 예제의 map이다. map의 숫자는 BFS로 탐색되는 차례입니다. 10(1,2,3)은 check 배열(이동 배열) 순서에 따라 다를 수 있다.
이 경우 큐에서 10(1)를 꺼내고 10(1) 10(1)칸 방문 체크 배열을 true바꾸고 11을 탐색하고 큐에 11을 넣는다. 하지만 11칸은 방문 체크 배열을 true 바꾸지 않고 있어 그 뒤에 10(2)를 큐에서 이동 가능한 칸인지 확인하면 방문 했다는 check가 되어있지 않아 다시 11칸을 큐에 추가한다. 이렇게 되면 q가 탐색해야할 칸이 많아져 효율성 테스트에서 실패를 할 수 있다.
