[백준] [BFS] 4486. 녹색 옷 입은 애가 젤다지?

4486. 녹색 옷 입은 애가 젤다지?

4485번: 녹색 옷 입은 애가 젤다지?

 

• 내 풀이 - python

from collections import deque
n=int(input())
dx=[-1,1,0,0]
dy=[0,0,-1,1]
cnt=0

def bfs(i,j):
    queue.append((i,j))
    lst[i][j]=graph[i][j]
  
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx= x+ dx[i]
            ny= y+ dy[i]
            if 0<=nx<n and 0<=ny<n:
                if lst[x][y]+graph[nx][ny]<lst[nx][ny]:
                    lst[nx][ny]=lst[x][y]+graph[nx][ny]
                    queue.append((nx,ny))

while n:
    cnt+=1
    graph=[]
    lst=[[int(1e9) for _ in range(n)] for _ in range(n)]
    queue=deque()
    for _ in range(n):
        graph.append(list(map(int,input().split())))
  
    bfs(0,0)
    result=lst[n-1][n-1]
  
    print(f'Problem {cnt}: {result}')
    n=int(input())

 

• java 코드

package dp;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class JUN4485_ParkSomin {
    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};
    public static int[][] graph;
    public static int[][] lst;

    static class Node{
        int x;
        int y;

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

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        int cnt = 0;

        while (n != 0) {
            cnt++;
            graph = new int[n][n];
            lst = new int[n][n];
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < n; j++) {
                    graph[i][j] = Integer.parseInt(st.nextToken());
                    lst[i][j] = Integer.MAX_VALUE;
                }
            }

            bfs(0,0);
            int result = lst[n-1][n-1];

            System.out.printf("Problem %d: %d\n", cnt, result);
            n = Integer.parseInt(br.readLine());
        }
        br.close();
    }

    public static void bfs(int i, int j) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(i, j));
        lst[i][j] = graph[i][j];

        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            int x = cur.x;
            int y = cur.y;

            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];

                if (nx < 0 || nx >= graph.length || ny < 0 || ny >= graph.length)
                    continue;

                if (lst[x][y] + graph[nx][ny] < lst[nx][ny]) {
                    lst[nx][ny] = lst[x][y] + graph[nx][ny];
                    queue.offer(new Node(nx, ny));
                }
            }
        }
    }
}