[프로그래머스] LV.2 게임 맵 최단거리

문제링크: 프로그래머스 Lv.2 게임 맵 최단거리

---

1. 아이디어

전형적인 bfs, dfs 문제. 단, 어떤 것을 사용할지 선택 필요.

• 최단거리로 도착점에 도착하면 값을 리턴하면 되기 때문에 bfs를 사용하여 이동을 한칸씩 늘려가며 탐색할 수 있는 bfs를 사용하기로 함.

2. 자료구조

• map과 동일한 크기의 방문체크 배열이 필요.
• bfs를 위한 Queue자료구조 필요.
• Queue에 넣을 포인트 클래스 필요.

3. 구현

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

public class Practice154 {
    static class Here {
        int x;
        int y;
        int cnt;

        public Here(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
    
    public static int solution(int[][] maps) {
        int[][] dir = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
        boolean[][] visited = new boolean[maps.length][maps[0].length];
        Queue<Here> queue = new LinkedList<>();

        queue.add(new Here(0, 0, 1));
        visited[0][0] = true;

        while(!queue.isEmpty()) {
            Here cur = queue.poll();
            if(cur.x == maps.length - 1 && cur.y == maps[0].length - 1) {
                return cur.cnt;
            }

            for (int[] d : dir) {
                int x = cur.x + d[0];
                int y = cur.y + d[1];
                if(x >= 0 && y >= 0 && x < maps.length && y < maps[0].length && maps[x][y] == 1 && !visited[x][y]) {
                    visited[x][y] = true;
                    queue.add(new Here(x, y, cur.cnt + 1));
                }
            }
        }
        return -1;
    }

4. 학습내용

• dfs로 탐색을 구현할 경우 효율성에서 문제가 생길 가능성도 있음.
• dfs로 구현할 경우 재귀를 사용하기 위해서는 클래스 맴버변수로 방문배열 등을 빼주는게 편리할 수 있음.

---

마지막 수정일시: 2022-10-11 11:03