문제 링크

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

문제 설명

• (0,0)에서 (h-1,w-1)까지 가는 최단거리 리턴

풀이

• BFS
• 자바로도 한 번 짜봤는데 ...

코드

Python

from collections import deque


def solution(maps):
    return bfs(maps)


def bfs(maps):
    dy, dx = [1,-1,0,0], [0,0,1,-1]
    dist = [[-1] * len(maps[0]) for _ in range(len(maps))] 
    dist[0][0] = 1
    q = deque([(0, 0)])
    while q:
        cy, cx = q.popleft()
        for d in range(4):
            ny, nx = cy + dy[d], cx + dx[d]
            if 0 <= ny < len(maps) and 0 <= nx < len(maps[0]):
                if dist[ny][nx] == -1 and maps[ny][nx] == 1:
                    dist[ny][nx] = dist[cy][cx] + 1
                    q.append((ny, nx))
    return dist[-1][-1]

Java

import java.util.LinkedList;
import java.util.Queue;

class Solution {

    int[][] maps, dist;
    int h, w;

    public int solution(int[][] maps) {
        this.maps = maps;
        h = maps.length;
        w = maps[0].length;
        dist = new int[h][w];
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++)
                dist[i][j] = -1;
        bfs();
        return dist[h-1][w-1];
    }

    void bfs(){
        int[] dy = {1,-1,0,0}, dx = {0,0,1,-1};
        dist[0][0] = 1;
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(0, 0));
        while(!q.isEmpty()){
            Node curr = q.poll();
            for(int d=0; d<4; d++){
                Node next = new Node(curr.y+dy[d], curr.x+dx[d]);
                if(0 <= next.y && next.y < maps.length && 0 <= next.x && next.x < maps[0].length){
                    if(dist[next.y][next.x] == -1 && maps[next.y][next.x] == 1){
                        dist[next.y][next.x] = dist[curr.y][curr.x] + 1;
                        q.add(next);
                    }
                }
            }
        }
    }
}

class Node{
    int y, x;
    Node(int y, int x){
        this.y = y; this.x = x;
    }
}