프로그래머스 - 게임 맵 최단거리 (JAVA)

 

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

 

접근 방식) BFS

1. 2차원 배열인 map을 상하좌우로 움직일거니까 static int[] dx, int[] dy 생성

움직인 거리 표시해줄 2차원 배열 static int visited[][] 생성

→ -1로 초기화해서 도착했든 못했든 상관 없이 -1 or 칸의 개수 최솟값 return 되게끔

2. BFS수행: 상하좌우 돌면서 map의 x, y에 벗어나지 않고, 방문하지 않았으면 큐에 추가하고 칸의 개수 1증가 시킴

 

 

→ 똑같은 BFS 방식인데 2가지로 풀어봤다. (프로그래머스 제출 후 시간 비교 사진 첨부)

1) int[] 배열 사용하여 Queue 생성

2) java.awt.Point 클래스 사용하여 Queue 생성 

 

 

1) int[] 배열 사용하여 Queue 생성 → 더 빠름

import java.util.*;
class Solution {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static int[][] visited;
    
    public int solution(int[][] maps) {
        visited = new int[maps.length][maps[0].length];
        
        BFS(maps, 0, 0);
        
        if (visited[maps.length - 1][maps[0].length - 1] == 0) 
            return -1;
        else 
            return visited[maps.length - 1][maps[0].length - 1];
    }
    
    static void BFS(int[][] maps, int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{i, j});
        visited[i][j] = 1;
        
        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            for (int k = 0; k < 4; k++) {
                int x = now[0] + dx[k];
                int y = now[1] + dy[k];
                
                if (x < 0 || y < 0 || x >= maps.length || y >= maps[0].length) continue;
                if (maps[x][y] == 1 && visited[x][y] == 0) {
                    visited[x][y] = visited[now[0]][now[1]] + 1;
                    queue.add(new int[]{x, y});
                }
            }
        }
    }
}

Queue<int[]> queue 사용

 

 

2) java.awt.Point 클래스 사용하여 Queue 생성

import java.util.*;
import java.awt.Point;
class Solution {
    static int[][] visited;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    
    public int solution(int[][] maps) {
        visited = new int[maps.length][maps[0].length];
        for (int i = 0; i < visited.length; i++) {
            for (int j = 0; j < visited[i].length; j++)
                visited[i][j] = -1;
        }
            
        BFS(maps, 0, 0);
        return visited[maps.length - 1][maps[0].length - 1];
    }
    
    static void BFS(int[][] maps, int i, int j) {
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(i, j));
        visited[i][j] = 1;
        
        while (!queue.isEmpty()) {
            Point now = queue.poll();
            for (int k = 0; k < 4; k++) {
                int x = now.x + dx[k];
                int y = now.y + dy[k];
                if (x >= 0 && y >= 0 && x < maps.length && y < maps[0].length) {
                    if (maps[x][y] != 0 && visited[x][y] == -1) {
                        visited[x][y] = visited[now.x][now.y] + 1;
                        queue.add(new Point(x, y));
                    }
                }
            }
        }
    }
}

java.awt.Point 클래스 사용