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

첫 시도

• dfs로 풀 수 있을 것 같았는데 bfs가 더 효율적일 것 같아 bfs로 해결
• bfs로 순회 시 목적지에 먼저 도착하는 거리가 필연적으로 최소값
• 목적지에 도착하지 못한다면 return -1
• 가독성을 위해 class를 만들어 순회했지만 효율성 측면에서 별로인지 효율성 테스트 실패
• class가 아닌 배열로 bfs 구현

해결

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import javax.management.remote.rmi._RMIConnection_Stub;
import javax.xml.soap.Node;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    int[][] maps;
    int[] dr = {0,-1,0,1};
    int[] dc = {-1,0,1,0};
    int bfs(){
        int n = maps.length;
        int m = maps[0].length;
        boolean[][] check = new boolean[n][m];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {0,0,1});

        while (!q.isEmpty()) {
            int[] temp = q.poll();
            int r = temp[0];
            int c = temp[1];
            int count = temp[2];
            if(r == n-1 && c == m-1){
                return count;
            }
            for(int i = 0; i < 4; i++){
                int nr = r + dr[i];
                int nc = c + dc[i];

                if(nr < 0 || nr >= n || nc < 0 || nc >= m || check[nr][nc] || maps[nr][nc] == 0) continue;
                q.add(new int[] {nr,nc,count+1});
                check[nr][nc] = true;
            }
        }
        return -1;
    }
    public int solution(int[][] maps) {
        this.maps = maps;
        int result = bfs();
        return result;
    }
    class Node{
        int r;
        int c;
        int count;

        public Node(int r, int c, int count) {
            this.r = r;
            this.c = c;
            this.count = count;
        }
    }
}

참고

• 직접구현