게임 맵 최단거리

https://school.programmers.co.kr/learn/courses/30/lessons/1844#

프로그래머스

 

BFS를 이용할 때는 큐에 넣기전에 방문 처리를 해주면 좋다. 뒤에 쌓여있는 동안 방문처리가 안되어서 해당 경로를 지나는 경로가 모두 큐에 들어가기 때문이다. 뒤에 들어간 것은 무조건 먼 거리기에 큐에 넣을 때 방문처리를 해주는 것이 좋다.

 

웬만하면 큐에 넣을 때 검증을 해주는 것이 좋다. 정답이든 방문이든

 

 

import java.io.*;
import java.util.*;
class Solution {
    public int solution(int[][] maps) {
        int[] move_r = {1,-1,0,0};
        int[] move_c = {0,0,1,-1};
        boolean[][] visited = new boolean[maps.length][maps[0].length];
        Queue<Node> q = new LinkedList<Node>();
        q.offer(new Node(0,0,1));
        visited[0][0]=true;
        
        while(q.size()>0){
            Node node = q.poll();
            
            for(int i=0; i<4;i++){
                Node new_Node = new Node(node.r+move_r[i],node.c+move_c[i],node.step+1);
                if(new_Node.r<maps.length&&new_Node.c<maps[0].length&&new_Node.r>=0&&new_Node.c>=0&&(!visited[new_Node.r][new_Node.c])&&(maps[new_Node.r][new_Node.c]==1)){
                    q.offer(new_Node);
                    visited[new_Node.r][new_Node.c]=true;
                    if(new_Node.r==maps.length-1&&new_Node.c==maps[0].length-1){
                        return new_Node.step;
                    }    
                }
            }           
        }
        return -1;
    }
    static class Node{
        public int r;
        public int c;
        public int step;
        
        public Node(int r, int c,int step){
            this.r=r;
            this.c=c;
            this.step=step;
        }
    }
}