[Programmers] 게임 맵 최단거리

[문제 링크]

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

프로그래머스

 

 

[풀이 과정]

 모든 경우의 수를 bfs알고리즘을 통해 풀었습니다.

 

[코드]

import java.util.*;

class Solution {
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};
    int[][] maps;
    boolean[][] visited; 
    int x;
    int y;

    public int solution(int[][] maps) {
        this.maps = maps;
        x = maps.length;
        y = maps[0].length;
        visited = new boolean[x][y];

        return bfs(0, 0);
    }

    public int bfs(int cx, int cy) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{cx, cy, 1});
        visited[cx][cy] = true;

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

            // 도착 체크
            if (q[0] == x - 1 && q[1] == y - 1) {
                return q[2];
            }

            for (int i = 0; i < 4; i++) {
                int nx = q[0] + dx[i];
                int ny = q[1] + dy[i];
                int nc = q[2] + 1;

                if (nx >= 0 && nx < x && ny >= 0 && ny < y &&
                    !visited[nx][ny] && maps[nx][ny] == 1) {
                    queue.add(new int[]{nx, ny, nc});
                    visited[nx][ny] = true;
                }
            }
        }

        return -1;
    }
}

[회고]

오랜만에 bfs문제를 풀었는데 정말 헷갈렸습니다.

여러번 틀리고 겨우겨우 답을 구현했습니다.

푸는 방법을 알아도 구현하는게 익숙하지가 않습니다.

그래도 나름 쉬운 문제였던 것 같습니다.

 

 

 

 

질문과 피드백은 언제나 환영입니다.

감사합니다.