[코딩테스트] 프로그래머스 - 게임 맵 최단거리(Java)

⭕ 설명

레벨:2
언어:Java

❔ 느낀점

내가 이문제 풀기전에 BFS문제를 한번 풀어본적이 있는데,
기업 코딩테스트시험보다가 3차원배열이란 BFS 문제 처음으로 접해보고 알고리즘을 풀어내가는방법에 그때 한번 풀어내고 해보니 할만하다싶어서 이문제를 찾아서 시도해봤습니다..

기본적인 BFS문제가 풀이방법이 비슷한데
1. BFS문제면 이동할때 사방팔방 다이동하고 그값을 저장하는 변수필요(큐 사용)
2. 위로 이동하고 좌우 옆으로 이동했을때 해당 좌우가 방문했는지 저장하는 변수필요(불 배열 사용)

• 이문제에서는 이동하는 횟수도 필요하여 Queue 제너릭타입을 Node static class 별도로 만들어서 x,y 좌표 및 이동한 횟수 저장해나간다.

정리하자면
1. 좌,우,상,하 이동할때마다 queue에 저장
2. 요구사항에 이동불가능한 장소 및 이동햇던 장소이면 boolean 배열에 저장
3. 이동한 값들 저장된 queue가 다 소진될때까지 루프
4. x, y 좌표값이 해당 사각형 경로 이탈시 체크 필요
5. 최종지점도착하는 이동값들있는데 최소값 비교하여 반환

이런식으로 흘러갑니다..

좋아요 많이받은코드는 awt 사용하는 point 클래스 활용했네요..
음 넵..

🗨 내가 작성한 코드

import java.util.*;

class Solution {
    
    static final int[] rowArr = new int[]{1, -1, 0, 0},
                        colArr = new int[]{0, 0, 1, -1};
    
    static class Node {
        final int row;
        final int col;
        final int move;
        
        public Node(int row, int col, int move){
            this.row = row;
            this.col = col;
            this.move = move;
        }
    }
    
    public int solution(int[][] maps) {
        int rowLength = maps.length, colLength = maps[0].length;
        boolean[][] visited = new boolean[rowLength][colLength];
        
        for(int i = 0; i < maps.length; i++) {
            for(int j = 0; j < maps[i].length; j++) {
                if(maps[i][j] == 0) visited[i][j] = true;
            }
        }
        
        
        Queue<Node> queue = new LinkedList<>();
        visited[0][0] = true;
        queue.offer(new Node(0, 0, 1));
        int min = Integer.MAX_VALUE;
        while(!queue.isEmpty()) {
            
            Node node = queue.poll();
            
            for(int i = 0; i < 4; i++) {
                int row = node.row + rowArr[i], col = node.col + colArr[i];
                if(rowLength <= row || row < 0 || colLength <= col || col < 0) continue;
                if(visited[row][col]) continue;
                
                visited[row][col] = true;
                queue.offer(new Node(row, col, node.move+1));
                if(row == rowLength - 1 && col == colLength - 1) min = Math.min(min, node.move + 1);
            }
         
        }
         
        return  min == Integer.MAX_VALUE ? -1 : min;
    }
   
}

🕑 가장 좋아요 많이받은 코드

좋아요가 1? (bfs 풀이법이 대체로 비슷한 결과인듯..)

import java.util.LinkedList;
import java.util.Queue;
import java.awt.Point;
class Solution {
    public static int solution(int[][] maps) {
        int X = maps[0].length;
        int Y = maps.length;
        boolean[][] visited = new boolean[Y][X];
        Queue<Point> q = new LinkedList<Point>();
        int x = 0;
        int y = 0;
        int size = 0;
        int cnt = 0;
        Point p = new Point();
        q.add(new Point(Y-1,X-1));
        while(q.isEmpty()==false) {
            size = q.size();
            cnt++;
            for(int i=0;i<size;i++)
            {
                p = q.peek();
                x = p.y;
                y = p.x;
                q.remove();
                if(visited[y][x]==true)
                    continue;
                maps[y][x] = 0;
                visited[y][x] = true;
                if(x==0 && y==0) {
                    return cnt;
                }
                if(x-1>-1 && maps[y][x-1]==1) { //왼쪽 한칸
                    q.add(new Point(y,x-1));
                }
                if(x+1<X && maps[y][x+1]==1) { //오른쪽 한칸
                    q.add(new Point(y,x+1));
                }
                if(y-1>-1 && maps[y-1][x]==1) { //위쪽 한칸
                    q.add(new Point(y-1,x));
                }
                if(y+1<Y && maps[y+1][x]==1) { //아래쪽 한칸
                    q.add(new Point(y+1,x));
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int arr[][] = {{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}};

        System.out.println(solution(arr));
    }

}