[프로그래머스] (JAVA) Lv2 게임 맵 최단거리

문제

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

프로그래머스

설명

입출력

나의 풀이

이 문제는 프로그래머스의 bfs/dfs 유형의 문제이고 최단거리를 구하는 문제이므로 bfs를 사용해야겠다는 생각이 들었다. 

문제를 풀기 위해서는 크게 bfs와 좌표 이동 구현 2가지가 사용된다.

그동안 좌표 이동 구현을 어렵게 생각해서 피하고 있었는데 더는 미루지 말자는 생각으로 도전해 보았다!!

문제를 풀기 전에 우선 좌표 이동에 대한 구현과 bfs를 구현해 보며 연습하는 과정을 거쳤다. 

좌표 이동 구현

package programmers.게임맵최단거리;

import java.util.Arrays;

public class 좌표이동 {
    public static void main(String[] args) {

        String move = "drrd";

        // 상하좌우
        int[] dr = {-1,1,0,0};
        int[] dc = {0,0,-1,1};

        // 방향을 저장할 변수 처음은 상(-1,0)
        int dir = 0; // 0,1,2,3 중에 가능(상하좌우)

        int[][] map = new int[3][3];

        // 처음 위치 (0,0)
        map[0][0] = 1;

        // 처음 위치 변수에 저장
        int r = 0;
        int c = 0;

        for(int[] m : map) {
            System.out.println(Arrays.toString(m));
        }

        for(int i=0; i < move.length(); i++) {
            char a = move.charAt(i);

            switch (a) {
                case 'u':
                    dir = 0;
                    break;
                case 'd':
                    dir = 1;
                    break;
                case 'l':
                    dir = 2;
                    break;
                case 'r':
                    dir = 3;
                    break;
            }

            r = r + dr[dir];
            c = c + dc[dir];

            map[r][c] = 1;

        }

        System.out.println();
        for(int[] m : map) {
            System.out.println(Arrays.toString(m));
        }

    }

}

처음부터 끝가지 구현해 보며 연습해 보며 좌표 평면에서의 이동을 코드로 구현하는 것에 대해 이해할 수 있었다.

일반적인 틀을 가지는 유형이기 때문에 자주 쓰며 익숙해지면 쉽게 구현할 수 있을 것 같다.

위의 코드를 바탕으로 실행한 결과 아래의 실행 결과를 통해 좌표이동을 눈으로 확인했다. 

bfs 구현

bfs를 처음 공부할 때 보는 일반적인 유형은 트리 형태의 예시가 주어지면

넓이 우선 탐색을 기준으로 탐색하는 전형적인 틀을 가진 bfs코드가 있는데 이를 직접 구현해 보며 연습해보았다. 

package programmers.게임맵최단거리;

import java.util.*;
public class test_bfs {

    static List<Integer>[] nodeList;
    static boolean[] visited;
    public static void main(String[] args) {
        int n = 6;
        int[][] node = {{1,2},{1,3},{2,4},{2,5}};

        nodeList = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            nodeList[i] = new ArrayList<>();
        }

        visited = new boolean[n];

        // 무방향 저장
        for (int[] e : node) {
            nodeList[e[0]].add(e[1]);
            nodeList[e[1]].add(e[0]);
        }

        bfs(1);
    }

    static public void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;
        queue.add(start);

        while (!queue.isEmpty()) {
            int now_node = queue.poll();
            System.out.print(now_node + " ");
            for (int i : nodeList[now_node]) {
                if (!visited[i]) {
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }

    }
}

실행 결과

문제 코드 구현

위에서 좌표이동과 bfs에 대해 공부하고 문제를 접근했더니 더 잘 이해가 되었다.

좌표 평면에서 최단 거리를 찾는 문제는 단 한 번도 풀어본 적이 없었기 때문에 아예 접근 방법조차 모르겠어서 

일반적인 풀이법을 참고하여 구현해 보았다.

import java.util.*;

class Solution {
    
    // 상하좌우
    static int[] dr = {-1,1,0,0};
    static int[] dc = {0,0,-1,1};
    
    public int solution(int[][] maps) {
        int answer = 0;
    
        // 방문 맵 체크용 맵 생성
        int[][] visited = new int[maps.length][maps[0].length];
        // 확인용
        //System.out.println(Arrays.deepToString(visited));
                
        bfs(maps, visited);
        
        answer = visited[maps.length - 1][maps[0].length - 1];
        
        if (answer == 0) {
            answer = -1;
        }
        
        return answer;
    }
    
    public static void bfs(int[][] maps, int[][] visited) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0,0});
        visited[0][0] = 1;
        
        while(!q.isEmpty()) {
            int[] current = q.poll();
            
            int r = current[0];
            int c = current[1];
            
            for(int i=0; i < 4; i++) {
                int mr = r + dr[i];
                int mc = c + dc[i];
                
                if(mr < 0 || mr > maps.length -1 || mc < 0 || mc > maps[0].length -1 ) {
                    continue;
                }
                
                if(visited[mr][mc] == 0 && maps[mr][mc] == 1) {
                    visited[mr][mc] = visited[r][c] + 1;
                    q.add(new int[]{mr, mc});
                }
            }
        }
    }
}

우선 맵의 크기와 같은 방문 확인 용 2차원 배열 visited를 생성한다. 

bfs함수 안에서 처음 위치인 (0,0)을 큐 안에 넣은 후 while문을 사용해 큐가 빌 때까지 즉, 모든 칸을 탐색하도록 하였다.

while문 안에서는 현재위치의 좌표를 행과 열에 따라 각각 r, c에 담은 후 for문을 4번 돈다. (4번은 각각 상하좌우 이동을 뜻한다.)

각각의 칸에 대해 for문을 4번 도는 동안 각각의 상하좌우의 칸에 대해 벽 또는 maps를 벗어났는지 확인한 후 

이동 가능한 칸에 대해 visited에 현재까지 이동한 칸의 개수를 넣어준 후 큐에 담기게 된다. 

이러한 과정을 반복하다 보면 벽을 제외한 모든 칸을 이동하게 된다.

 

모든 노드를 방문한 후 visited를 확인해 보면 

벽을 제회한 칸에 대해 각각의 칸마다 시작 지점으로부터의 최단거리의 이동수가 찍혀있다.

코드로만 보면 잘 이해가 안 됐는데 그림도 그려보고 방문 배열도 확인해 보니 각각의 칸마다 확인을 하며

최단 거리를 알 수 있는 bfs를 좀 더 이해할 수 있게 되었다.