[programmers] 게임 맵 최단거리

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

프로그래머스

 

---

< 게임 맵 최단거리 >

 

문제 풀이 (Java)

import java.util.*;

class Solution {
	public int solution(int[][] maps) {
		int answer = -1;

		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { 0, 0, 1 });

		boolean visited[][] = new boolean[maps.length][maps[0].length];
		visited[0][0] = true;

		int dx[] = { -1, 1, 0, 0 };
		int dy[] = { 0, 0, -1, 1 };

		boolean flag = false;

		while (!queue.isEmpty()) {
			int info[] = queue.poll();

			for (int i = 0; i < 4; i++) {
				int x = info[0] + dx[i];
				int y = info[1] + dy[i];

				if (x >= 0 && x < maps.length && y >= 0 && y < maps[0].length && maps[x][y] == 1 && !visited[x][y]) {
					if (x == maps.length - 1 && y == maps[0].length - 1) {
						answer = info[2] + 1;
						flag = true;
						break;
					}
					visited[x][y] = true;
					queue.add(new int[] { x, y, info[2] + 1 });
				}
			}
			if (flag) {
				break;
			}
		}
		return answer;
	}
}

 

Queue에 시작 위치와 지나가야 하는 칸의 개수를 저장한 뒤 Queue가 빌 때까지 다음 과정을 반복한다.

 

1. queue poll

2. 상하좌우 탐색하며 maps 범위 안이고 벽이 없는 자리이며 아직 방문하지 않은 곳이라면 방문 표시 및 queue에 추가. 이때, 이동한 위치가 우측 하단이라면 answer 업데이트 후 종료

 

최종 answer을 반환한다. 

 

---

---

 

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges