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

문제

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

 

1번 	
maps = [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]	
answer = 11

2번
maps = [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]	
answer = -1

 

최단거리의 경우 전체 경로를 다시 돌아가서 하는 stack을 이용하는 bfs로 하면 효율성이 떨어진다 

그러므로 queue를 통해 다시 돌아가는 것이 아닌 해당 queue를 넣어 바로 빼는 방식으로 동작하는 dfs를 이용하는 것이 맞다 

 

우선 dfs / bfs의 경우 현재위치에서 4방향(위 , 아래 , 왼쪽 , 오른쪽)으로 이동하여 현재 경로를 변경하므로 이를 배열로 저장해야한다 

그리고 특정 조건에 따라 가능한 경로만 이동해야한다.

1. 이동한 경로가 이동해서는 안되는 경로일경우 제외를 하는 로직이 필요하다 

예를 들어 최초 시점인 0,0 에서 왼쪽으로 이동하면 -1,0이 되는데 0 미만인 경우 존재하지 않는 경로이니 이를 제외해야한다 

2.이미 목적지에 도착을 했다면 더이상 4방향으로 수행해서는 안된다 

예를 들어 0,0이 시작점이고 1,1 까지 도달해야한다고 하면 1,1 이미 도착을 했다면 최단거리를 이미 구했기 때문에 다시 돌아가서 구하면 안된다 

3. 이미 방문했던 경로는 다시 돌아가면 안된다 

예를 들어 0,0에서 출발해서 1,0으로 갈 경우 1,0 경로를 다시 4방향으로 돌리게 되는데 0,0의 경우 이미 방문한 경로이기에 다시 들어가서는 안된다 , 이에 따라 방문여부를 표기하여 이미 방문을 했으면 다시 들어가지 않는 규칙이 필요하다 

 

이를 정리하여 코드로 확인해보자 

int mx = map.length;
int my = map[0].length;

int arrayX = {0,0,1,-1};
int arrayY = {1,-1,0,0};

현재 경로 
int[] k = {0,1};

int[][] visited = new int[mx][my];
//처음은 무조건 방문을 하므로 1을 삽입한다 
visited[0][0] = 1;

for(int i=0; i<4; i++){
	int m = k[0] +arrayX[i];	
    int n = k[1] +arrayY[i];
    //존재하지 않는 영역 ( 음수일경우 수행하지 않음 ) 
    if(m <0 || n <0){
    	continue;
    }
    //이동 경로가 도착지의 경로(여기서는 마지막 좌표)일 경우 통과시킨다. 
    if(m >=mx || n >=nx){
    	continue;
    }
    if(visited[m][n] ==1){
    	continues;
    }
    //방문을 하면 기존 방문에 대상을 삽입한다 
    visited[m][n] = 기존방문 +1; 
    
}

 

이제 문제를 풀어보자 

public int solution(int[][] map){
    int maxX = map.length;
    int maxY = map[0].length;

    int[] arrayX = {1,-1,0,0};
    int[] arrayY = {0,0,-1,1};

    int[][] visited = new int[maxX][maxY];
    visited[0][0] = 1;

    Queue<int[]> queue = new LinkedList<>();
    queue.add(new int[]{0,0});

    while(!queue.isEmpty()){
        int[] nowDestination = queue.poll();
        int x = nowDestination[0];
        int y = nowDestination[1];

        for(int i=0; i<4; i++){
         int mx =   x+arrayX[i];
         int my =   x+arrayY[i];     
            if(mx <0 || my <0 || mx >= maxX || my >= maxY){
                continue;
            }
            if(visited[mx][my] ==1 && map[mx][my]==0){
                continue;
            }

            visited[mx][my] = visited[x][y]+1;
            queue.offer(new int[]{mx,my});
        }
    }
    
    return visited[mx-1][my-1] ==0 > -1 :      visited[mx-1][my-1]
       
}