관리 메뉴

막내의 막무가내 프로그래밍 & 일상

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

알고리즘/DFS, BFS, 시뮬, 백트래킹

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

막무가내막내 2021. 4. 18. 22:28
728x90

 

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

 

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

[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1

programmers.co.kr

 

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

 

단순한 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

알고리즘 문제풀이 연습. Contribute to mtjin/algorithm_practice development by creating an account on GitHub.

github.com

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

 

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

 

 

 

728x90
Comments