-
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