SWEA 1249. [S/W 문제해결 응용] 4일차 - 보급로

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

---

문제 풀이

 

높이 정보를 입력받은 뒤 최소값으로 목표지점까지 도달할 수 있게 하였다.

 

1. 높이정보를 기준으로 한 우선순위 큐를 생성한 뒤, bfs를 돌려 탐색을 한다.

2. 목표지점에 도착한다면 도착한 노드의 최소시간과 정답을 비교하여 값을 갱신하여 준다.

 

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.PriorityQueue;
 
public class Solution {
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static int[][] map;
    static boolean[][] visited;
 
    static class Node implements Comparable<Node>{
        int x;
        int y;
        int height;
        int time;
 
        public Node(int x, int y, int height, int time) {
            this.x = x;
            this.y = y;
            this.height = height;
            this.time = time;
        }
 
        @Override
        public int compareTo(Node o) {
            return this.time - o.time;
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        int T = Integer.parseInt(br.readLine());
 
        for(int test_case = 1; test_case <= T; test_case++) {
            int N = Integer.parseInt(br.readLine());
 
            map = new int[N][N];
            visited = new boolean[N][N];
 
            for(int i = 0; i < N; i++) {
                String str = br.readLine();
 
                for(int j = 0; j < N; j++) {
                    map[i][j] = str.charAt(j) - '0';
                }
            }
 
            PriorityQueue<Node> q = new PriorityQueue<>();
            int result = Integer.MAX_VALUE;
 
            q.add(new Node(0, 0, map[0][0], 0));
            visited[0][0] = true;
 
            while(!q.isEmpty()) {
                Node poll = q.poll();
 
                int nx = poll.x;
                int ny = poll.y;
                int time = poll.time;
 
                if(nx == N - 1 && ny == N - 1) {
                    result = Math.min(result, time);
                    continue;
                }
 
                for(int i = 0; i < 4; i++) {
                    int x = nx + dx[i];
                    int y = ny + dy[i];
 
                    if(x < 0 || y < 0 || x >= N || y >= N || visited[x][y]) {
                        continue;
                    }
 
                    q.add(new Node(x, y, map[x][y], time + map[x][y]));
                    visited[x][y] = true;
                }
            }
 
            sb.append("#" + test_case + " ").append(result).append("\n");
        }
 
        System.out.println(sb);
    }
}