게임 맵 최단거리

Java

import java.util.*;
class Solution {
    int length = -1;
    int[] x = {-1, 0, 1, 0};
    int[] y = {0, 1, 0, -1};
    int[][] map;
    public int solution(int[][] maps){
        int answer = 0;
        bfs(maps);
        return length;
    }
    
    private void bfs(int[][] maps){
        Queue<C> que = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        
        que.add(new C(0, 0, 0));
        
        while(!que.isEmpty()){
            C c = que.poll();
            if(c.x == maps.length - 1 &&
               c.y == maps[0].length - 1){
                if(length == -1 || length > c.count + 1){
                    length = c.count + 1;
                    return;
                }
            }
            
            for(int i = 0; i < 4; i++){
                int x1 = c.x + x[i];
                int y1 = c.y + y[i];
                if(x1 >= 0 && y1 >= 0 && x1 < maps.length && y1 < maps[0].length &&
                   maps[x1][y1] == 1 && maps[x1][y1] != 3){
                    que.add(new C(x1, y1, c.count + 1));
                    maps[x1][y1] = 3;
                }
            }
            
            
        }
    }
    
    private class C {
        int x;
        int y;
        int count;
        
        C(int x, int y, int count){
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }
    
//     시간초과
//     int length = -1;
//     public int solution(int[][] maps) {
//         int answer = 0;
//         root(maps, 0, 0, 0);
//         return length;
//     }
    
//     private int root(int[][] mapvisited, int x, int y, int count){
//         int[][] pictureCopy = Arrays.stream(mapvisited).map(int[]::clone).toArray(int[][]::new);
//         if(x < 0 || y < 0 || 
//            x >= mapvisited.length || y >= mapvisited[x].length || mapvisited[x][y] == 0){
//             return 0;
//         }
//         if(x == mapvisited.length - 1 && y == mapvisited[x].length - 1){
//             if(length > count + 1 || length == -1){
//                 length = count + 1;
//             }
//             return 0;
//         }
        
//         pictureCopy[x][y] = 0;
        
//         return root(mapvisited, x + 1, y, count + 1)+
//         root(pictureCopy, x - 1, y, count + 1)+
//         root(pictureCopy, x, y + 1, count + 1)+
//         root(pictureCopy, x, y - 1, count + 1);
        
        
            
//     }
}

Python

from collections import deque

xy = ((-1, 0), (1, 0), (0, -1), (0, 1))
length = -1

def solution(maps):
    bfs(maps)
    return length

def bfs(maps):
    global length
    global xy
    que = deque()
    que.append([0, 0, 0])
    
    while que:
        x, y, count = que.popleft()
        if x == (len(maps) - 1) and y == (len(maps[x]) - 1):
            if length == -1 or length > (count + 1):
                length = count + 1
                return
        
        for i in xy:
            x1 = i[0] + x
            y1 = i[1] + y
            
            if x1 >= 0 and y1 >= 0 and x1 < len(maps) and y1 < len(maps[x]) and maps[x1][y1] == 1 and maps[x1][y1] != 3:
                que.append([x1, y1, count + 1])
                maps[x1][y1] = 3