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

🧫 문제 분석

✔️ 출처

게임 맵 최단거리 level 2

📖 문제

dfs/bfs 문제이다. bfs로 풀면 좋을것 같아서 bfs로 방향을 잡았다.
방문한 좌표에 대해 check를 해주고, 갈 수 있는 곳을 check해주는 것이 핵심이다.

처음에 visited를 q에서 뽑고나서 true로 해주어서 무한 루프에 빠졌었는데
중복 좌표값이 Queue 에 추가되서 그런거였다.

1 2
3 4

그래프가 이렇게 있고
Queue에 2,3 순으로 들어가 있다고 하자.

2가 나와서 4를 추가한다.
3이 나와서 4를 추가한다. << 이런 중복 좌표값이 생긴다.
이를 해결하기 위해서 while문 밖에서 시작지점에 true를 미리 넣어주고
가능한 좌표일때 방문 표시를 즉시 해줌으로써 해결하였다.

 

---

🔅 문제 풀이

import java.util.*;

class Solution {
    static int[] dxarr = {0, 0, 1, -1};
    static int[] dyarr = {1, -1, 0, 0};
    
    public int solution(int[][] maps) {
        boolean[][] visited = new boolean[maps.length][maps[0].length];
        int answer = bfs(visited, maps);
        return answer;
    }
    
    public int bfs(boolean[][] visited, int[][] map) {
        Queue<int[]> q = new LinkedList<>();
        visited[0][0] = true;
        q.add(new int[]{0,0});
        
        while(!q.isEmpty()) {
            int[] coord = q.poll();
            
            for(int i = 0; i < 4; i++) {
                int dx = coord[1] + dxarr[i]; // 열
                int dy = coord[0] + dyarr[i]; // 행

                if (dx >= 0 && dx < map[0].length && dy >= 0 && dy < map.length) {
                    if(!visited[dy][dx] && map[dy][dx] >= 1) {
                        map[dy][dx]+= map[coord[0]][coord[1]]; // 이전 거리를 더한다.
                        q.add(new int[]{dy, dx});
                        visited[dy][dx] = true;
                    }
                } 
            }
        }
        
        int endPoint = map[map.length - 1][map[0].length - 1];
        return  endPoint == 1 ? -1 : endPoint;
    }
}

---

❗ 오답노트 / 필요한 지식

1. 깊이/너비 탐색문제 오랜만에 시도해보니 좀 어려웠다. 다시 개념을 정리하고 많이 풀어보자.