[programmers] 게임 맵 최단거리

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

프로그래머스

 

dfs로 푼 풀이

바로 떠올라서 풀었던 부분

import java.util.*;

class Solution {
    static int n, m;
    static int[][] routes;
    static int[][] maps1;
    public int solution(int[][] maps) {
        int answer = 0;
        n = maps.length;
        m = maps[0].length;
        routes = new int[n][m];
        maps1 = maps;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                routes[i][j] = -1;
            }
        }        
        
        routes[n - 1][m - 1] = 1;
        search(n - 1, m - 1, routes[n - 1][m - 1]);
        
        // System.out.println(Arrays.deepToString(routes));
        
        return routes[0][0];
    }
    
    public void search(int x, int y, int cnt) {
        if (x - 1 >= 0 && (routes[x - 1][y] == -1 || routes[x - 1][y] > cnt + 1) && maps1[x - 1][y] == 1) {
            routes[x - 1][y] = cnt + 1;
            search(x - 1, y, cnt + 1);
        }
        if (y - 1 >= 0 && (routes[x][y - 1] == -1 || routes[x][y - 1] > cnt + 1) && maps1[x][y - 1] == 1) {
            routes[x][y - 1] = cnt + 1;
            search(x, y - 1, cnt + 1);
        }
        if (x + 1 < n && (routes[x + 1][y] == -1 || routes[x + 1][y] > cnt + 1) && maps1[x + 1][y] == 1) {
            routes[x + 1][y] = cnt + 1;
            search(x + 1, y, cnt + 1);
        }
        if (y + 1 < m && (routes[x][y + 1] == -1 || routes[x][y + 1] > cnt + 1) && maps1[x][y + 1] == 1) {
            routes[x][y + 1] = cnt + 1;
            search(x, y + 1, cnt + 1);
        }
    }
}

 

bfs로 푼 풀이

dfs로 풀었을 때 시간복잡도를 줄일 방법이 딱히 생각이 안났음

아예 접근부터 바꿔야하나해서 bfs로 다시 풀어봄

import java.util.*;

class Solution {
    
    public int solution(int[][] maps) {
        int answer = -1;
        int n = maps.length;
        int m = maps[0].length;
        
        Queue<int[]> queue = new LinkedList<>();
        
        queue.add(new int[]{0, 0, 1});
        boolean[][] visited = new boolean[n][m];
        visited[0][0] = true;
        
        while(!queue.isEmpty()) {
            int[] temp = queue.poll();
            
            int x = temp[0];
            int y = temp[1];
            int cnt = temp[2];
            
            if (x == n - 1 && y == m - 1) {
                answer = cnt;
                break;
            }
            
            if (x - 1 >= 0 && !visited[x - 1][y] && maps[x - 1][y] == 1) {
                visited[x - 1][y] = true;
                queue.add(new int[]{x - 1, y, cnt + 1});
            }
            if (y - 1 >= 0 && !visited[x][y - 1] && maps[x][y - 1] == 1) {
                visited[x][y - 1] = true;
                queue.add(new int[]{x, y - 1, cnt + 1});
            }
            if (x + 1 < n && !visited[x + 1][y] && maps[x + 1][y] == 1) {
                visited[x + 1][y] = true;
                queue.add(new int[]{x + 1, y, cnt + 1});
            }
            if (y + 1 < m && !visited[x][y + 1] && maps[x][y + 1] == 1) {
                visited[x][y + 1] = true;
                queue.add(new int[]{x, y + 1, cnt + 1});
            }
        }
        // System.out.println(Arrays.deepToString(routes));
        
        return answer;
    }
}