99클럽 코테 스터디 10일차 TIL, DFS,BFS(게임 맵 최단 거리)

1. 문제 정의

 

2. 문제 접근

 

bfs를 통해 최단거리를 구해주면 될 것 같다.

3. 문제 풀이

1. bfs를 통해 최단거리 맵을 만든다.
2. 원하는 좌표의 최단거리를 리턴한다.

4. 코드

import java.util.*;

class Solution {
    int n, m;
    int[][] dist;
    boolean[][] visit;
    int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
    public int solution(int[][] maps) {
        // int answer = 0;
            n = maps.length;
        m = maps[0].length;
        dist = new int[n][m];
        visit = new boolean[n][m];

        bfs(maps);

        return dist[n-1][m-1] == 0 ? -1 : dist[n-1][m-1]+1;
    }
    
    private void bfs(int[][] maps){
       Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0});
        visit[0][0] = true;

        while (!q.isEmpty()) {
            int[] temp = q.poll();
            for (int k = 0; k < 4; k++) {
                int dx = temp[0] + dir[k][0];
                int dy = temp[1] + dir[k][1];

                if (dx < 0 || dy < 0 || dx >= n || dy >= m) continue;
                if (maps[dx][dy] == 0) continue;
                if (visit[dx][dy]) continue;

                visit[dx][dy] = true;
                q.add(new int[]{dx, dy});
                dist[dx][dy] = dist[temp[0]][temp[1]] + 1;
            }
        }
        
    }
}

5. 회고

bfs를 이용하면 최단거리를 구할 수 있다. 또는 2차원 배열 위에서 움직임에 대한 무언가를 구할 수 있다. 확실히 bfs가 dfs보다 나에게는 더 쉬운 것 같다....