[프로그래머스 찾아라 프로그래밍 마에스터] 게임 맵 최단거리

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

코딩테스트 연습 - 게임 맵 최단거리

import java.util.LinkedList;
import java.util.Queue;

class Solution {
	    public int solution(int[][] maps) {
	        int answer = 0;
	        
	        boolean flag=false;
	        int n=maps.length;
	        int m=maps[0].length;
	        int []dx= {-1,1,0,0};
	        int []dy= {0,0,-1,1};
	        
	        boolean visited[][]=new boolean[n][m];
	        Queue <int[]> queue= new LinkedList<>();
	        queue.offer(new int[] {0,0});
	        visited[0][0]=true;
	        
	    out:  while(!queue.isEmpty()) {
	        	answer++;
	        	int size=queue.size();
	        	
	        	for(int i=0; i<size; i++) {
	        		int []point = queue.poll();
	        		
	        		for(int d=0; d<4; d++) {
	        			int nx=point[0]+dx[d];
	        			int ny=point[1]+dy[d];
	        			
	        			if(nx<0 || ny<0 || nx>=n || ny>=m || visited[nx][ny] || maps[nx][ny]==0) continue;
	        			if(nx==n-1 && ny==m-1) {
	        				flag=true;
	        				break out;
	        			}
	        			visited[nx][ny]=true;
	        			queue.offer(new int[] {nx, ny});
	        		}
	        		
	        	}
	        }
	        
	        if(!flag) return -1;
	        return answer+1;
	    }
	}

소요시간 : 18분

 

 

전형적인 bfs문제입니다.

갈 수 없는 부분을 체크해주기 위해서 flag를 줘서 체크했습니다.

 

너무 쉬운 문제라 딱히 설명할 게 없습니다

 

끝!