99클럽 코테 스터디 35일차 TIL , 게임 맵 최단거리

문제

풀이

입력으로 map이 주어진다. 첫 번째 자리 (0,0)에서 시작해 map의 가장 끝 (n, m) 자리까지 가는데 최소거리가 얼마나 되는지 return 하는 문제이다. 만약 가지 못하는 경우라면 -1을 뱉는다.

최솟값이기 때문에 BFS를 가지고 풀이해야겠다고 생각했다.

제출 1 - 정답

import java.util.*;
class Solution {
    public int solution(int[][] maps) {
        int answer = bfs(maps);

        return answer == 0 ? -1 : answer;
    }
    private int bfs(int[][] maps){

        int rowSize = maps.length;
        int colSize = maps[0].length;

        int[][] visited = new int[rowSize][colSize];	//방문배열

        Deque<int[]> que = new ArrayDeque<>();

        int[] dx = {-1,0,1,0};
        int[] dy = {0,1,0,-1};

        que.offer(new int[]{0,0,1});
        visited[0][0] = 1;

		//목표하는 곳에 값이 들어갔다면 최소 거리이므로 종료됨
        while(!que.isEmpty() && visited[rowSize-1][colSize-1] == 0){
            int[] tmp = que.poll();
            for(int i=0;i<4;i++){
                int nx = tmp[0] + dx[i];
                int ny = tmp[1] + dy[i];
                int val = tmp[2];
                if(nx < 0 || ny < 0
                        || nx >= rowSize || ny >= colSize
                        || maps[nx][ny] == 0 || visited[nx][ny] != 0) continue;

                que.offer(new int[]{nx,ny,val+1});
                visited[nx][ny] = val + 1;
            }
        }

        return visited[rowSize-1][colSize-1];
    }
}

큐에 넣을 때 좌표 값과 시작점에서 거리를 넣어준다.

BFS이기 때문에 목표지점에 값이 들어가게 되면 while문을 통해 종료하게 된다.

제출 2 - 정답

import java.util.*;
class Solution {
    public int solution(int[][] maps) {
        int answer = bfs(maps);

        return answer == 1 ? -1 : answer;
    }
    private int bfs(int[][] maps){

        int rowSize = maps.length;
        int colSize = maps[0].length;

        Deque<int[]> que = new ArrayDeque<>();

        int[] dx = {-1,0,1,0};
        int[] dy = {0,1,0,-1};

        que.offer(new int[]{0,0,1});

        while(!que.isEmpty() && maps[rowSize-1][colSize-1] == 1){
            int[] tmp = que.poll();
            for(int i=0;i<4;i++){
                int nx = tmp[0] + dx[i];
                int ny = tmp[1] + dy[i];
                int val = tmp[2];
                if(nx < 0 || ny < 0
                        || nx >= rowSize || ny >= colSize
                        || maps[nx][ny] != 1) continue;

                que.offer(new int[]{nx,ny,val+1});
                maps[nx][ny] = val+1;
            }
        }

        return maps[rowSize-1][colSize-1];
    }
}

 

풀이는 했지만 조금 더 간단하게 바꿨다.

일단 visited배열을 없애고 해당 map을 직접 바꿔 주었다. 그래서 maps가 continue 하는 조건도 1이 아닐 경우로 바꾸어줬고 while문 조건도 maps의 목표지점을 확인하는 것으로 바꿔줬다. 이게 가능한 이유는 n, m의 사이즈는 1일 수 있지만 둘 다 1일 수는 없다는 조건이 있기 때문에 가능했다.

TIL

• BFS학습