[프로그래머스] 게임 맵 최단거리

 

programmers.co.kr/learn/courses/10302/lessons/62951

[Java/문제풀이] 코딩테스트 광탈 방지 Kit: Java편 - Step 1. 게임 맵 최단거리 직접 풀어보기

로직

그렇게 어렵지는 않았다

최단거리 문제는 보통 BFS가 유리하다. 단 path를 다 기억해야하는 경우에는 DFS 방식을 사용하는 것이 좋다.

처음에는 x, y좌표를 어떻게 queue에 넣을까 하다가 그냥 Node라는 inner class를 만들어서 진행했다.

(inner Class 만들면 뭔가 Node라고 이름붙여야할 것같아서 Node라 했지만, 나중에 다른 분들 코드를 보니까 Point라는 이름이 더 적절했을 것같다)

 

로직은 BFS, 그게 전부다

코드

import java.util.*;
class Solution {
    int final_x, final_y;
	public int solution(int[][] maps) {

        int[][] distances = new int[maps.length][maps[0].length];
        final_x = maps.length - 1;
        final_y = maps[0].length - 1;
        if(final_x == 0 && final_y == 0){
            return 0;
        }
        
        bfs(maps, distances);
        if(distances[final_x][final_y] != 0){
            return distances[final_x][final_y];
        }
		return -1;
	}

    void bfs(int[][] maps, int[][] distances){
        Queue<Node> queue = new LinkedList<Node>();
        Node start = new Node(0, 0);
        queue.offer(start);
        distances[0][0] = 1;
        while(queue.peek() != null){
            Node n = queue.poll();
            int x = n.getX();
            int y = n.getY();
            
            if(distances[final_x][final_y] != 0) break;
            
            int distance = distances[x][y];
            
            if(x > 0 && maps[x - 1][y] == 1){
                update(x - 1, y, distance, queue, distances);
            }
            if(x < final_x && maps[x + 1][y] == 1){
                update(x + 1, y, distance, queue, distances);
            }
            if(y > 0 && maps[x][y - 1] == 1){
                update(x, y - 1, distance, queue, distances);
            }
            if(y < final_y && maps[x][y + 1] == 1){
                update(x, y + 1, distance, queue, distances);
            }
        }
        
    }
     void update(int x, int y, int distance, Queue queue, int[][] distances){
            if(distances[x][y] == 0){
                queue.offer(new Node(x, y));
                distances[x][y] = distance + 1;
            }
        }
    
    private class Node{
        int x, y;
        Node(int x, int y){
            this.x = x;
            this.y = y;
        }
        int getX(){
           return this.x; 
        }
        int getY(){
            return this.y;
        }
    }
}