🎯2주차B "게임 맵 최단거리"

🎃문제설명

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

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.

두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.

만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

🔒제한사항

maps	answer
[[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]]	11
[[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]]	-1

💾입출력 예

입출력 예 #1
주어진 데이터는 다음과 같습니다.

캐릭터가 적 팀의 진영까지 이동하는 가장 빠른 길은 다음 그림과 같습니다.

따라서 총 11칸을 캐릭터가 지나갔으므로 11을 return 하면 됩니다.

입출력 예 #2
문제의 예시와 같으며, 상대 팀 진영에 도달할 방법이 없습니다. 따라서 -1을 return 합니다.

---

🌟문제 이해 및 풀이계획

✏️처음에는 DFS로 문제를 푸려고 했는데 그러면 백트래킹을 해서 다시 돌아가야 하나? 하고 생각이 복잡했었다. 안되는 것은 아니지만 최단거리를 최대한 빨리 도달하기 위해서는 BFS가 더 좋은 방법 인 것 같다.
✏️효율성 면에서 시간초과가 나길래 visited배열을 따로 두지 않으려고 지나온 길을 0으로 만들어 줬는데 왜 시간초과가 날까 생각했다. 문제는 큐에 들어가는 길은 아직 방문처리가 되지 않기 때문에 중복으로 들어가는 것이 문제였다.
=> 결국 visited배열을 두어 큐에 들어가는 길을 방문처리 하여 중복으로 큐에 들어가지 않도록 처리했더니 효율성 테스트를 통과했다.

import java.util.*;

class Solution {
    static boolean[][] visited;
    
    // 나의 위치정보, 현재까지 이동거리 
    public static class Location {
    	int x, y, move;

	public Location(int x, int y, int move) {
    	    this.x = x;
            this.y = y;
            this.move = move;
        }
    }
    
    public int solution(int[][] maps) {
        int n = maps.length; // 행의 길이
        int m = maps[0].length; // 열의 길이
        
        return bfs(maps, n, m);
    }
    
    public static int bfs(int[][] maps, int n, int m) {
    	Queue<Location> q = new LinkedList<Location>();
        visited = new boolean[n][m];
        int cur_x = 0;
        int cur_y = 0;
        int cur_move = 1; // 현재까지 이동 거리
        q.add(new Location(cur_x, cur_y, cur_move));
		
        while(!q.isEmpty()) {
           Location location = (Location) q.poll();
           cur_x = location.x;
           cur_y = location.y;
           cur_move = location.move;
           System.out.println(cur_x + " " + cur_y);
			
            // 방문 체크 // 지나간 길은 0으로 만들어 준다.
            maps[cur_x][cur_y] = 0; 
            visited[cur_x][cur_y] = true;
			
            for(int i=0; i<4; i++) {
                if(cur_x + dx[i] >= 0 && cur_x + dx[i] < n && cur_y + dy[i] >= 0 && cur_y + dy[i] < m && !visited[cur_x + dx[i]][cur_y + dy[i]]) { // 맵의 범위 안에 있을 때
                    // 갈 수 있는 길일 때
                    if(maps[cur_x+dx[i]][cur_y+dy[i]] == 1) {
                        if(cur_x+dx[i] == n-1 && cur_y+dy[i] == m-1) { // 상대팀 진영에 도착 시
                            cur_move += 1;
                            return cur_move;
                        }
                        visited[cur_x + dx[i]][cur_y + dy[i]] = true;
                        q.add(new Location(cur_x+dx[i], cur_y+dy[i], cur_move+1));
                    }
                }
            }
    	}
		
    	return -1;
    }
}

🍭강의내용

✔️너비우선탐색(BFS)의 전형적인 문제
✔️사방으로 갈 수 있는 길을 모두 탐색해 보는 것. (벽과 다녀온 길 제외)
✔️나는 규칙을 만들고, 연산은 컴퓨터가!

✍🏻강의 코드

import java.util.*;

class Solution {
    
    class Position { // 현재 위치 클래스
        int x, y;
        
        Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
        
        boolean isValid(int width, int height) {
            if(x < 0 || x >= width) return false;
            if(y < 0 || y >= height) return false;
            return true;
        }
    }
    
    public int solution(int[][] maps) {
        int mapHeight = maps.length;
        int mapWidth = maps[0].length;
        
        // BFS : Queue // 인터페이스로만 제공. 큐를 구현하는 여러 오브젝트 중 LinkedList를 사용한다.
        Queue<Position> queue = new LinkedList<>();
        int[][] count = new int[mapHeight][mapWidth];
        boolean[][] visited = new boolean[mapHeight][mapWidth];
        
        queue.offer(new Position(0, 0));
        count[0][0] = 1;
        visited[0][0] = true;
        
        while(!queue.isEmpty()) {
            Position current = queue.poll();
            
            int currentCount = count[current.y][current.x];
            
            // 4가지 경우 
            final int[][] moving = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
            for(int i=0; i<moving.length; i++){
                // 생성자 필요!
                Position moved = new Position(current.x + moving[i][0], current.y + moving[i][1]);
                
                if(!moved.isValid(mapWidth, mapHeight)) continue;
                if(visited[moved.y][moved.x]) continue;
                if(maps[moved.y][moved.x] == 0) continue; // 0: 벽, 1: 길
                
                count[moved.y][moved.x] = currentCount + 1;
                visited[moved.y][moved.x] = true;
                queue.offer(moved);
            }
            
        }
        
        int answer = count[mapHeight-1][mapWidth-1];
        if(answer == 0) return -1;

        return answer;
    }
}

💡나의 풀이는 dx, dy를 따로 두어 각각 더해줬는데 moving배열로 한번에 처리하는 것도 좋은 방법인 것 같다!
💡x, y와 mapWidth, mapHeight의 각각의 위치가 헷깔리는데 코드 작성 시 정확히 어느 위치에 들어가야 하는지 확인해야 할 것 같다.