게임맵 최단거리

문제 

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

cf) 문제의 양이 너무 많아서 링크로 대체 합니다. 

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

 

풀이 

주요생각 

4방향으로 이동 하여 거리를 이동하되 음수 이거나 이미 방문 했을 경우는 재방문을 하지 않는다 

4방향  = { {1,0} , {0,1} , {-1,0} , {0,-1} }

방문 여부 boolean[][] visited 

queue에 저장될 값은 해당 좌표의 위치와 현재 거리를 얼마나 이동햇는지에 대한 값이 필요하다 

좌표가 마지막으로 이동하면 작업을 종료하고 해당 값을 반환한다 

만약 그전에 queue에 대상이 없어서 종료가 되면 -1을 반환하도록 한다 

 

   public int solution(int[][] maps) {
   	int[][] array = { {1,0} ,{0,1} ,{-1,0},{0,-1} };
   	int x = maps.length;
    int y = maps[0].length;
    boolean[][]visited = new boolean[x][y];
    Queue<int[]> queue = new LinkedList<>();
    
    queue.add(new int[]{0,0,1});
    visited[0][0] = 1;
    while(!queue.isEmpty()){
		    int[] poll = queue.poll();
            int pollX = poll[0];
            int pollY = poll[1];        
            int answer = poll[2];  
            if(pollX == x-1 && pollY == y-1){
                return answer 
            }
        for(int i=0; i<array.length;i++){
            int[] depth = array[i];
            int depthX = pollX+depth[0];
            int depthY = pollY+depth[1];            
			
            if(depthX>=0 && depthY>=0 && depthX <x && depthY <y
            && !visited[depthX][depthY]
            && maps[depthX][depthY] !=0){
            	queue.add(new int[]{depthX,depthY,answer+1})
            }
        }
    
    }
    
   	return -1;
   }