[프로그래머스/JAVA 자바] 게임 맵 최단거리

 

프로그래머스

문제풀이

1. 현재 위치에서 4방향 탐색을 하기 위한 dx , dy 배열을 생성.

2. 방문 확인 , 최단거리 카운트를 위한 vist 배열 생성.

3. bfs 탐색 사용. 시작 위치 1로 카운트 ( visit [ 0 ] [ 0 ] = 1 )

4. 4방 탐색 후 , 갈 수 있는 곳인지 방문 했던곳인지 검사

5. 위 검사가 가능하면 이동한 visit를 이동하기전 visit + 1 로 설정

6. 이 과정을 4방향 모두 이동할 수 없을 때 까지 반복

 

구현코드

import java.util.*;

class Solution {
    
    static int[] dx = { 1, 0, -1, 0 };
	static int[] dy = { 0, 1, 0, -1 };
    
    public int solution(int[][] maps) {
        int answer = 0;

		int[][] visit = new int[maps.length][maps[0].length];
		visit[0][0] = 1;

		bfs(maps, visit);
		answer = visit[maps.length - 1][maps[0].length - 1];
		if (answer == 0) {
			answer = -1;
		}
        
        return answer;
    }
    
    static void bfs(int[][] maps, int[][] visit) {

		Queue<int[]> queue = new LinkedList<>();

		queue.add(new int[] { 0, 0 });

		while (!queue.isEmpty()) {

			int[] now = queue.poll();
			int x = now[0];
			int y = now[1];

			for (int i = 0; i < 4; i++) {

				int nx = x + dx[i];
				int ny = y + dy[i];

				if (nx >= 0 && nx < maps.length && ny >= 0 && ny < maps[0].length && visit[nx][ny] == 0
						&& maps[nx][ny] == 1) {
					visit[nx][ny] = visit[x][y] + 1;
					queue.add(new int[] { nx, ny });
				}

			}

		}

	}
    
}