[프로그래머스] 1844 게임 맵 최단거리 (Lv.2) - BFS

문제

게임 맵 최단거리

코드

• 풀이 방법

1. {x좌표, y좌표}를 저장한 큐를 선언하고 방문 여부 체크와 좌표 별 이동 거리를 저장할 int[][] 배열을 선언한다.

Queue<int[]> q = new LinkedList<>();
q.offer(new int[] {0, 0});
int[][] visited = new int[maps.length][maps[0].length];
visited[0][0] = 1;

2. 상, 하, 좌, 우를 돌며 이동 가능한 좌표라면 큐에 삽입하고 이동 거리를 visited 배열에 삽입(방문 처리)한다.

for (int i = 0; i < 4; i++) {
    int cx = current[0] + dx[i];
    int cy = current[1] + dy[i];

    if (cx >= 0 && cx < maps.length && cy >= 0 && cy < maps[0].length) {
        if (visited[cx][cy] == 0 && maps[cx][cy] == 1) {
            q.offer(new int[] {cx, cy});
            visited[cx][cy] = visited[current[0]][current[1]] + 1;
        }
    }
}

3. 1번과 2번을 반복하다 완료 조건이 나오면 종료한다.

if (current[0] == maps.length -1 && current[1] == maps[0].length -1) return visited[current[0]][current[1]];

전체 코드

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

class Solution {
    int[] dx = {-1, 1, 0, 0}; // 상, 하, 좌, 우
    int[] dy = {0, 0, -1, 1}; // 상, 하, 좌, 우

    public int solution(int[][] maps) {
        return bfs(maps);
    }

    public int bfs(int[][] maps) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {0, 0});
        int[][] visited = new int[maps.length][maps[0].length];
        visited[0][0] = 1;

        while (!q.isEmpty()) {
            int[] current = q.poll();
            if (current[0] == maps.length -1 && current[1] == maps[0].length -1) return visited[current[0]][current[1]];

            for (int i = 0; i < 4; i++) {
                int cx = current[0] + dx[i];
                int cy = current[1] + dy[i];

                if (cx >= 0 && cx < maps.length && cy >= 0 && cy < maps[0].length) {
                    if (visited[cx][cy] == 0 && maps[cx][cy] == 1) {
                        q.offer(new int[] {cx, cy});
                        visited[cx][cy] = visited[current[0]][current[1]] + 1;
                    }
                }
            }
        }
        return -1;
    }
}