프로그래머스 - 게임 맵

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

코딩테스트 연습 - 게임 맵 최단거리

 

 

 

 

 

그래프 탐색 문제이다. 예전에 풀었던 백준 토마토 문제(https://www.acmicpc.net/problem/7576)와 비슷하다고 생각해서 Queue를 사용한 BFS 알고리즘으로 풀었다.

 

Player 클래스를 만들어 좌표 값과 이동한 칸 수를 저장하도록 했다.

 

 

 

 

코드

import java.util.*;

class Solution {
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static boolean[][] visited;
    
    static class Player {
        int x;
        int y;
        int count;
        
        public Player(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }
    
    public int solution(int[][] maps) {
        visited = new boolean[maps.length][maps[0].length];
        
        int answer = bfs(maps, 0, 0);
        
        return answer;
    }
    
    public int bfs(int[][] maps, int a, int b) {
        Queue<Player> queue = new LinkedList<Player>();
        
        queue.add(new Player(a, b, 1));
        
        while(!queue.isEmpty()) {
            Player player = queue.poll();
            visited[player.x][player.y] = true;
            
            if(player.x == maps.length - 1 && player.y == maps[0].length - 1) {
                return player.count;
            }
            
            for(int i = 0; i < 4; i++) {
                int nx = player.x + dx[i];
                int ny = player.y + dy[i];
                int count = player.count;
                
                if(0 <= nx && nx < maps.length && 0 <= ny && ny < maps[0].length) {
                    if(maps[nx][ny] == 1 && !visited[nx][ny]) {
                        queue.add(new Player(nx, ny, count + 1));
                        visited[nx][ny] = true;
                    }
                }
            }
        }
        
        return -1;
    }
}

 

 

 

 

 

결과

정확성과 효율성 모두 통과했다!