[알고리즘] 프로그래머스 게임 맵 최단거리 (찾아라 프로그래밍 마에스터) -BFS- 자바

 

programmers.co.kr/learn/courses/30/lessons/1844?language=java

코딩테스트 연습 - 게임 맵 최단거리

 

오랜만에 프로그래머스 문제를 풀어봤습니다. ㅎㅎ

 

단순한 BFS 문제입니다. 그러므로 풀이생략 !!

 

[Java]

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

class Solution {
    private static boolean[][] isVisited;
    private static int[] dr = new int[]{-1, 0, 1, 0};
    private static int[] dc = new int[]{0, -1, 0, 1};
    private static int answer = Integer.MAX_VALUE;

    private static void bfs(int[][] maps) {
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(0, 0, 0));
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            if (point.r== maps.length-1 && point.c == maps[0].length-1) { //도착지점
                answer = Math.min(answer, point.cnt+1);
                return;
            }
            for (int i = 0; i < 4; i++) {
                int r2 = point.r + dr[i];
                int c2 = point.c + dc[i];
                if (r2 >= 0 && r2 < maps.length && c2 >= 0 && c2 < maps[0].length && maps[r2][c2] == 1 && !isVisited[r2][c2]) {
                    queue.add(new Point(r2, c2, point.cnt + 1));
                    isVisited[r2][c2] = true;
                }
            }
        }
    }

    public int solution(int[][] maps) { // 0:벽, 1:길
        isVisited = new boolean[maps.length][maps[0].length];
        bfs(maps);
        if(answer == Integer.MAX_VALUE) answer = -1;
        return answer;
    }

    private static class Point {
        int r;
        int c;
        int cnt;

        Point(int r, int c, int cnt) {
            this.r = r;
            this.c = c;
            this.cnt = cnt;
        }
    }
}

 

 

github.com/mtjin/algorithm_practice/blob/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20%EA%B2%8C%EC%9E%84%20%EB%A7%B5%20%EC%B5%9C%EB%8B%A8%EA%B1%B0%EB%A6%AC%20(%EC%B0%BE%EC%95%84%EB%9D%BC%20%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D%20%EB%A7%88%EC%97%90%EC%8A%A4%ED%84%B0)%20-BFS-%20%EC%9E%90%EB%B0%94/Solution.java

mtjin/algorithm_practice

(요즘 여러 사정으로 바빠 알고리즘을 못풀었는데 당분간은 안드로이드 프로젝트와 기존에 푼 알고리즘 문제 복습에 집중하려고 합니다. )

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!