[PGM]게임 맵 최단거리

티어 : Lv. 2
정답여부 : 오답

💡문제

● 게임 맵 최단거리

 

💡입출력 예

💡문제 분석 요약 

• 상대팀 전역에 도착할수 있는 최단거리를 출력

 

💡알고리즘 설계

• answer : 거리 계산
• dx ,dy : 좌,우,위,아래
• visited : 방문확인

1. 각 열 , 행 길이를 넣어줌
2. visited 방문배열에 길이넣어줌
3. BFS 0,0시작하여 maps과 같이 넣어줌
4. 0,0 시작하며 있는 위치는 1라고 가정 방문했음으로 visited true 변경
5. 만약 해당 경로에 도착했으면 answer에 넣고 break
6. 상하좌우 탐색하면서 만약 x 와 y가 0보다 작거나 n과 m보다 큰 경우는 만약 0을 만난경우
   • 벽을 만난 경우로 continue 패스
7. 만약 방문하지 않았고 1인 경우는 que에 추가하여 탐색

 

💡시간복잡도

• O(NM)

 

💡코드

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    static int N;
    static int arr[][];
    static boolean visited[][];
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public int solution(int[][] maps) {
        N = maps.length;
        arr = new int[N][N];
        visited = new boolean[N][N];

        // 맵 복사 및 거리 초기화
        for (int i = 0; i < maps.length; i++) {
            for (int j = 0; j < maps[i].length; j++) {
                arr[i][j] = maps[i][j];
            }
        }

        // BFS 호출
        return BFS(0, 0);
    }

    public static int BFS(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = true;
        arr[x][y] = 1; // 시작점의 거리 초기화

        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int poll_x = poll[0];
            int poll_y = poll[1];

            // 목적지 도달 확인
            if (poll_x == N - 1 && poll_y == N - 1) {
                return arr[poll_x][poll_y]; // 도달한 위치의 거리 반환
            }

            for (int i = 0; i < 4; i++) {
                int nextX = dx[i] + poll_x;
                int nextY = dy[i] + poll_y;

                // 범위 체크 및 이동 가능 여부 확인
                if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < N && !visited[nextX][nextY] && arr[nextX][nextY] == 1) {
                    queue.offer(new int[]{nextX, nextY});
                    visited[nextX][nextY] = true; // 체크
                    arr[nextX][nextY] = arr[poll_x][poll_y] + 1; // 거리 업데이트
                }
            }
        }

        return -1; // 도달 불가능
    }
}

 

💡 틀린 이유

정확성이 떨어진다고 틀림 ㅜㅜ

다른분 코드를 보니 간단하게 구현한 분이 있어서 가져왔다.

깔끔하고 앞으로 이렇게 풀어야 겠다는 생각이..

 

💡 틀린 부분 수정 or 다른 풀이

import java.util.*;

class Solution {
    public static int n, m;
    public static int answer = -1;
    
    public static int dx[] = {-1, 1, 0, 0};
    public static int dy[] = {0, 0, -1, 1};
    public static boolean visited[][];
    
    public int solution(int[][] maps) {
        n = maps.length;
        m = maps[0].length;
        visited = new boolean[n][m];
    
        return bfs(0, 0, maps);
    }
    
    public int bfs(int x, int y, int[][] maps){
        Queue<int[]> que = new LinkedList<>();
    
        que.add(new int[]{x, y, 1});
        visited[0][0] = true;

        while (!que.isEmpty()) {
            int temp[] = que.poll();
            x = temp[0];
            y = temp[1];
            int count = temp[2];
            
            if (x == n-1 && y == m-1) {
                answer = count;
                break;
            }

            for (int i = 0; i<4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if(maps[nx][ny] == 0) continue;
                if(!visited[nx][ny] && maps[nx][ny] == 1) {
                    visited[nx][ny] = true;
                    que.add(new int[]{nx, ny, count+1});
                }
            }
        }

        return answer;
    }
}

 

💡 느낀점

오랜만이라서 생각이 잘 안난다.