[Programmers]-게임 맵 최단거리

문제

위와 같은 문제가 있다고 보자.

1,1 좌표의 캐릭터가 빨간 지점까지 가는 최단거리를 구하면된다.

코드

import java.util.*;

class Solution {
    int[] dirX = {0, 0, 1, -1};
    int[] dirY = {1, -1, 0, 0};
    boolean[][] visited ;
    int m,n;
    
    public int solution(int[][] maps) {
        int answer = 0;
        m = maps[0].length;//가로
        n = maps.length;//세로
        visited = new boolean[n][m];
        
        answer = bfs(0,0,maps);
        
        return answer;
    }
    
    
    public int bfs(int x, int y, int[][] maps){
        
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x,y,1));
        visited[y][x] = true;
        
        while(!q.isEmpty()){//큐가 비어있을 때 까지
            Node node = q.poll();//큐에 담기
            if(node.x == m-1 && node.y == n-1)//빨간 지점에 도착하면
                return node.cost;
            
            for(int i=0;i<4;i++){//상하좌우 가기위해
                int xx = node.x + dirX[i];
                int yy = node.y + dirY[i];
                
                if(0<=xx && xx<m && 0<=yy && yy<n){//맵 범위 조건
                    if(maps[yy][xx]==1 && !visited[yy][xx]){//벽,방문 조건
                        visited[yy][xx] = true;//방문처리
                        q.offer(new Node(xx,yy,node.cost+1));//조건 되면 큐에 넣기
                    }
                }
            }
        }
        return -1;//while문 끝나도 도착 못하면
    }
    
    public class Node{
        int x;
        int y;
        int cost;
        
        public Node(int x, int y, int cost){//생성자
            this.x = x;
            this.y = y;
            this.cost = cost;
        }
    }
}

코드 설명

x,y좌표를 같이 큐에 넣고싶었는데 그걸 생각하다가 클래스를 새로만들어 생성해주었다.

나머지는 주석으로 달아주었다.

요약

• 최단거리에는 bfs를 떠올리자.
• 조금더 bfs에 가까워 졌다.