프로그래머스 - 게임 맵 최단거리

프로그래머스 - 게임 맵 최단거리

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

class Solution {
	int[][] maps;
	int[][] visited;

	public int solution(int[][] maps) {
		// bfs로 가면서 우, 하, 상, 좌 순으로 하면 최단거리?

		this.maps = maps;
		this.visited = new int[maps.length][maps[0].length];

		return bfs(0, 0);
	}

	private int bfs(int startY, int startX) {
		// 시작 칸 방문
		visited[0][0] = 1;
		// 상, 하, 좌, 우 순
		int[] dx = new int[] {0, 0, -1, 1};
		int[] dy = new int[] {-1, 1, 0, 0};
		Queue<Integer> queue = new LinkedList<>();
		queue.add(startY);
		queue.add(startX);

		while (!queue.isEmpty()) {
			int targetY = queue.poll();
			int targetX = queue.poll();

			// 종료점이라면 목표 도달
			if (targetY == maps.length - 1 && targetX == maps[0].length - 1) {
				return visited[targetY][targetX];
			}

			int nextY = 0;
			int nextX = 0;

			for (int i = 0; i < dx.length; i++) {
				nextY = targetY + dy[i];
				nextX = targetX + dx[i];

				if (nextX >= 0 && nextX < maps[0].length && nextY >= 0 && nextY < maps.length) {
					// 0이면 방문한 것이 없는 것임
					if (visited[nextY][nextX] == 0 && maps[nextY][nextX] == 1) {
						visited[nextY][nextX] = visited[targetY][targetX] + 1;
						// 만일 경로가 2개가 된다면 그 지점에서 두곳을 각각 들림!!
						// 위, 우측 이라면 -> 위, 우측 큐 삽입 -> 위 갔다가 갈 수 있는곳 큐에 추가 
                        // -> 오른쪽 갔다가 갈 수 있는곳 큐에 추가
						// 따라서 도착하자마자 바로 그냥 끝내버리기가 가능!
						queue.add(nextY);
						queue.add(nextX);
					}
				}
			}
		}
		// 여기 온거면 도달 못한 것
		return -1;
	}
}

• 경로가 여러개라면 당연히 아래로 가는 경우나 오른쪽으로 가는 경우가 제일 최선의 경로라 생각하고, 하 -> 우 -> 상 -> 좌 순으로 탐색하면서 하나라도 갈 수 있으면 바로 break를 했다.
• 하지만 일부 케이스가 실패했다. 왜냐하면 이게 그 칸에서 갈 수 있지만, 그 다음칸에서 만약 벽을 만나면 못가니깐 실패해버린다.
• visited 배열을 boolean으로만 활용했었는데, 해당 칸에 도달했을 때의 이동 수를 저장함으로써 boolean의 기능과 횟수 저장 두가지 기능이 가능하다.
  • 0이라면 아직 방문하지 않은 것
• 하 그리고 나는 만약 경로가 위로가는 경로랑 우측 경로가 있으면, 위로가면 쭉 계속 위부터 돌겠지 했는데, 이건 큐다! 상, 하, 좌, 우 를 하니깐 상, 우를 큐에 넣고 상을 갔었을테고, 그 다음엔 무조건 우를 간다!!
  • 아래 그림에서 좌측 테이블에서 형광펜 표시가 2번째로 가는 곳!
  • 그림으로 보면 이해가 갈듯!
    

• 그래서 이 부분을 놓쳐서 계속 고민했던 것 같다.. 결론적으론 갈 수 있는 곳을 한번씩 가니깐 최초 도달이 무조건 최단 경로!!
• 나도 좀 고민한 만큼, 고민하는 누군가에게 도움이 되는 게시글이길!