프로그래머스 레벨2 게임 맵 최단거리

요즘 DFS BFS 문제만 푸는 거 같다.

 

이번에 푼 문제..!

 

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

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

 

게임 맵 최단거리다.

 

모든 코드는 GitHub 에 올려놓았다.

 

 

일단 코드부터 보자

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

class Solution {
    public int solution(int[][] maps) {

            // 상하좌우
        int[] moveX = {-1, 1, 0, 0};
        int[] moveY = {0, 0, -1, 1};
        
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(0,0));

        while (!queue.isEmpty()) {

            Node node = queue.poll(); // 값을꺼냄
            //현재 노드 좌표 꺼내기
            int x = node.getX();
            int y = node.getY();

            for(int i=0; i<4; i++) { //상하좌우 탐색 시작

                //새롭게 이동할 노드
                int mX = x + moveX[i];
                int mY = y + moveY[i];

                //밖인지 확인하기 또는 벽
                if(mX <= -1 || mX >= maps.length || mY <= -1 || mY >= maps[0].length || maps[mX][mY] == 0) {
                    continue;
                }


                if(maps[mX][mY] == 1) {
                    maps[mX][mY] = maps[x][y] + 1; 
                    queue.add(new Node(mX, mY));
                }

            }

        }
        int answer = maps[maps.length - 1][ maps[0].length -1];
        return answer != 1 ? answer : -1;
    }
}

class Node {

    private int x;
    private int y;

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

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
}

일단 0,0을 Node 클래스에 x y를

저장해주고 queue 에서 빼면서

 

BFS 탐색을 해준다. 

 

그리고 벽인지. 밖인지를 확인해주고 값을 증가시켜나간다

 

그림으로 보면 아래와 같이 된다.

 

 

위 사진 처럼 시작하면

 

 

 

순차적으로 탐색을하며 노드 간 거리를 기록하게 되고

 

갈림길이 나와도 BFS 탐색이므로 위 사진처럼 탐색을 하게 된다.!

 

DFS.. 와 BFS에 익숙해져 가고 있다..

 

다음 포스팅도 탐색이다.!