[알고리즘]프로그래머스 1844번 - 게임 맵 최단거리

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

프로그래머스 1844번 - https://programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스 1844번 - https://programmers.co.kr/learn/courses/30/lessons/1844

 

요구사항

1. 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 반환하라.

2. 검은색 부분은 벽이며, 벽으로 막힌 칸은 지나갈 수 없습니다.

3. 게임 맵을 벗어난 칸은 갈 수 없습니다.

4. 캐릭터는 (1, 1) 위치에 있으며, 상대 팀 진영은 (n, m) 위치에 있습니다.

 

요구사항 분석 및  풀이과정

1. 이 문제와 같은 방법으로 풀면 됩니다.

2. 다른 점은 그래프(또는 트리)로 구성된 것이 아니라 배열로 구성되어있다는 점입니다.

3. 게임 맵을 벗어나지 않고, 벽으로 막힌 칸은 지나갈 수 없는 점을 고려하여 4방향으로 BFS 탐색을 진행하면 됩니다.

4-1. 각 칸에 처음 도착했을 시점에 지나온 칸의 개수가 캐릭터의 시작 점에서 해당 칸까지 오는데 필요한 최소 칸의 개수입니다.

4-2. 즉, 이미 도착한 칸이라면 방문할 필요가 없다는 의미입니다.

 

소스코드 작성

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

class Solution {

	private final static int[] dx = {1, -1, 0, 0};
	private final static int[] dy = {0, 0, -1, 1};
	private final static int WALL = 0;

	private static class Pair {

		private final int x;
		private final int y;

		public Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}

		public int getX() {
			return x;
		}

		public int getY() {
			return y;
		}
	}

	public int solution(int[][] maps) {
		int n = maps.length;
		int m = maps[0].length;

		Queue<Pair> q = new LinkedList<>();
		int[][] distance = new int[n][m];

		q.offer(new Pair(0, 0));
		distance[0][0] = 1;

		while (!q.isEmpty()) {
			Pair current = q.poll();
			int currentX = current.getX();
			int currentY = current.getY();

			for (int dir = 0; dir < 4; dir++) {
				int nextX = currentX + dx[dir];
				int nextY = currentY + dy[dir];

				if (nextX < 0 || nextX >= m || nextY < 0 || nextY >= n) {
					continue;
				}

				if (maps[nextY][nextX] == WALL || distance[nextY][nextX] != 0) {
					continue;
				}

				distance[nextY][nextX] = distance[currentY][currentX] + 1;
				q.offer(new Pair(nextX, nextY));
			}
		}

		return distance[n - 1][m - 1] == 0 ? -1 : distance[n - 1][m - 1];
	}
}

 

결과

 

소스코드 깃허브 주소

링크