[Lv.2] 게임 맵 최단거리 : Java

프로그래머스

 

 

 

이해하기

일단 떠올렸던 아이디어는 BFS와 사방탐색을 사용하자 였는데... 이걸 어떻게 구현해야 할지 감이 안 온단 말이에요ㅠ

진짜 ㅋㅋ... 사방탐색 좌표 (1, 0), (-1, 0), (0, 1), (0, -1)까지 노트에 적고 그 이상 나아가질 못했다.

 

 

문제풀이

[프로그래머스] 게임 맵 최단거리(Java 자바)

이번에 참고한 블로그는 요기...

 

import java.util.*;

class Solution {
    int[] dX = {1, -1, 0, 0};
    int[] dY = {0, 0, 1, -1};

    public int solution(int[][] maps) {
        int answer = 0;

        int[][] visited = new int[maps.length][maps[0].length];

        bfs(maps, visited);
        answer = visited[maps.length - 1][maps[0].length - 1];

        if (answer == 0) {
            answer = -1;
        }

        return answer;
    }

    public void bfs(int[][] maps, int[][] visited) {
        int x = 0;
        int y = 0;
        visited[x][y] = 1;

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int cX = current[0];
            int cY = current[1];

            for (int i = 0; i < 4; i++) {
                int nX = cX + dX[i];
                int nY = cY = dY[i];

                if (nX < 0 || nX > maps.length - 1 || nY < 0 || nY > maps[0].length - 1) {
                    continue;
                }

                if (visited[nX][nY] == 0 && maps[nX][nY] == 1) {
                    visited[nX][nY] = visited[cX][cY] + 1;
                    queue.add(new int[]{nX, nY});
                }
            }
        }
    }
}

 

코드만 보고 하나씩 생각해보았다.

 

    int[] dX = {1, -1, 0, 0};
    int[] dY = {0, 0, 1, -1};

 

일단 이 부분은 사방탐색을 위한 좌표.

 

        int[][] visited = new int[maps.length][maps[0].length];

 

처음엔 boolean이어야 하지 않나? 했지만 이 문제는 최단 거리를 찾는 문제이니 거리를 저장하기 위해서는 int 배열을 사용하는 것이 맞았다.

 

        bfs(maps, visited);

 

여기서부터는 bfs 함수를 살펴보자.

 

    public void bfs(int[][] maps, int[][] visited) {
        int x = 0;
        int y = 0;
        visited[x][y] = 1;

 

일단 내 캐릭터는 0, 0에서 시작하는 것이 확실하니 x = 0, y = 0 으로 초기화한 후 visited[x][y] = 1로 만들어준다.

이 부분부터 거리 세기가 시작된다.

 

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});

 

Queue를 하나 만들어주고 첫 좌표인 [x, y]부터 담아준다.

 

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int cX = current[0];
            int cY = current[1];

 

queue가 비어있지 않는 한 while문을 계속 돈다.

current라는 배열을 통해 queue.poll()의 값을 받아온 후 cX, cY를 초기화한다.

 

            for (int i = 0; i < 4; i++) {
                int nX = cX + dX[i];
                int nY = cY = dY[i];

 

for문을 돌며 사방 탐색을 한다.

 

                if (nX < 0 || nX > maps.length - 1 || nY < 0 || nY > maps[0].length - 1) {
                    continue;
                }

 

만약 nX나 nY가 맵의 범위를 넘어서게 되면 continue한다.

 

                if (visited[nX][nY] == 0 && maps[nX][nY] == 1) {
                    visited[nX][nY] = visited[cX][cY] + 1;
                    queue.add(new int[]{nX, nY});
                }

 

아직 방문하지 않았고 (and) 맵의 해당 부분이 벽이 아니라면 if문을 실행한다.

visited[nX][nY] 의 값은 이전 값인 visited[cX][cY]의 값에 1을 더한 값으로 한다. (한 칸 더 이동했다고 봄)

queue에 [nX, nY]의 좌표를 넣고 다시 while문 처음으로 돌아간다.

 

 

코드를 보고는 이해가 됐지만 비슷한 문제가 나온다고 해서 다시 풀 수 있을지가 의문이다 ㅜㅅㅜ

BFS, DFS 공부 열심히 해야지...