[프로그래머스/java] 게임 맵 최단거리 - BFS 사용

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

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

 

 

시작위치에서 목적지까지 최단거리를 구하는 문제는 무조건 BFS로 풀어야한다.

 

최단거리를 구하는 문제는 BFS 만한 것이 없다.

 

import java.util.*;

class Solution {
	int[] dy = {1, 0, -1, 0};
	int[] dx = {0, 1, 0, -1};
	boolean[][] visit;
	
    public int solution(int[][] maps) {
    	int n = maps.length;
    	int m = maps[0].length;
    	
        visit = new boolean[n][m];
    	int answer = Integer.MAX_VALUE;
        
        Queue<Pos> q = new LinkedList<Pos>();
        q.add(new Pos(0,0,1));
        while(!q.isEmpty()) {
        	Pos temp = q.poll();
        	
        	if(temp.y == n-1 && temp.x == m-1) {
        		answer = Math.min(answer, temp.cnt);
        		continue;
        	}
        	
        	for (int dir = 0; dir < 4; dir++) {
				int ny = dy[dir] + temp.y;
				int nx = dx[dir] + temp.x;
				
				if(ny < 0 || nx < 0 || ny >= n || nx >= m || visit[ny][nx]) continue;
				if(maps[ny][nx] == 0) continue;
				
				visit[ny][nx] = true;
				int cnt = temp.cnt + 1;
				q.add(new Pos(ny, nx, cnt));
			}
        }
        
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
}

class Pos {
	int y, x, cnt;
	
	public Pos(int y, int x, int cnt) {
		this.y = y;
		this.x = x;
		this.cnt = cnt;
	}
}