ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • SWEA 1249. [S/W 문제해결 응용] 4일차 - 보급로
    PS 2023. 11. 18. 01:19

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

     

    SW Expert Academy

    SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

    swexpertacademy.com


    문제 풀이

     

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

     

    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);
        }
    }

    'PS' 카테고리의 다른 글

    SWEA 1767 프로세서 연결하기  (1) 2024.02.28
    SWEA 1954. 달팽이 숫자  (0) 2023.11.18
    SWEA 1206. [S/W 문제해결 기본] 1일차 - View  (0) 2023.11.16
    Java 1253 좋다  (0) 2023.09.11
    Java 1654 랜선 자르기  (0) 2023.08.29
Designed by Tistory.