백준 : 1261

https://www.acmicpc.net/problem/1261

1261번: 알고스팟

일단 우선순위 큐를 사용하지않고 단순 큐를 사용해서도 빠른 속도로 구해진다.

문제의 해법은 digit[N][M] 크기의 2차원 크기의 배열을 INF 큰값으로초기화하고

Q에 좌표값과 현재까지 깬 돌의 횟수를 넣어서 돌린다. 그리고 digit의 값과 현재 Q에담긴 횟수를 비교회서 digit을 초기화해주면 가장 적은 벽돌로 N,M 지점까지의 최소값을 구할수가 있다.

 

지금은 단순큐를 사용하였지만 문제를 풀때 우선순위 큐를 사용한다면 가장 효율적인 좌표 즉 돌은깬횟수가 적은 좌표를 먼저 위로올리고 처리하면서 빠르게 문제를 해결할수도 있다.

 

package com.ssay.algo;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class B1261 {
    static int M, N;
    static int Map[][];
    static int digit[][];
    static int dy[] = { 0, 0, -1, 1 };
    static int dx[] = { 1, -1, 0, 0 };
 
    public static class Bj {
        public int y;
        public int x;
        public int crush;
 
        public Bj(int y, int x, int crush) {
            this.y = y;
            this.x = x;
            this.crush = crush;
        }
 
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
 
        Map = new int[N][M];
        digit = new int[N][M];
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for(int j=0;j<M;j++) {
                Map[i][j] = str.charAt(j) - '0';
            }
        
        }
        
        for(int i=0;i<N;i++) {
            Arrays.fill(digit[i], Integer.MAX_VALUE);
        }
        
        
        Queue<Bj> q = new LinkedList<Bj>();
 
        q.add(new Bj(0, 0, 0));
        digit[0][0] = 0;
        
        
        while (!q.isEmpty()) {
 
            Bj tmp = q.poll();
            int y = tmp.y;
            int x = tmp.x;
            int crush = tmp.crush;
            
            for(int d=0;d<4;d++) {
                int ny = y+ dy[d];
                int nx = x+ dx[d];
                
                if(ny<0||nx<0||nx>=M||ny>=N) continue;
                
                if(Map[ny][nx] == 0) {
                    if(digit[ny][nx] > crush) {
                        digit[ny][nx] = crush;
                        q.add(new Bj(ny,nx,digit[ny][nx]));
                    }
                }else {
                    if(digit[ny][nx] > crush +1) {
                        digit[ny][nx] = crush +1;
                        q.add(new Bj(ny,nx,digit[ny][nx]));
                    }
                    
                }
                
            }
        }
        
        System.out.println(digit[N-1][M-1]);
 
    }
}