-
[SWEA] 1249 보급로 - Java알고리즘 문제 풀이 2024. 5. 21. 01:38
문제 - 보급로
접근 방법
- 이 문제는 2차원 배열 문제이고 bfs 문제이다 0,0 을 시작으로 n,n 끝까지 가는 길에 최소의 시간으로 도착을 하는 문제이다
- 갈때마다 최소의 숫자를 계속 찾아야 하므로 우선순위 큐를 사용해서 낮은 것 부터 탐색을 하면 될 것 같다
코드 작성
import java.util.PriorityQueue; import java.util.Queue; import java.io.*; class Solution { static int[] dx = { -1, 1, 0, 0 }; static int[] dy = { 0, 0, -1, 1 }; static boolean[][] visited; static int[][] map; static int N; static int min; public static void main(String[] args) throws Exception { try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) { int testCount = Integer.parseInt(br.readLine()); for (int i = 0; i < testCount; i++) { N = Integer.parseInt(br.readLine()); map = new int[N][N]; visited = new boolean[N][N]; min = Integer.MAX_VALUE; for (int j = 0; j < N; j++) { String s = br.readLine(); for (int k = 0; k < N; k++) { map[j][k] = s.charAt(k) - '0'; } } bfs(0, 0); System.out.println("#" + (i + 1) + " " + min); } } } public static void bfs(int x, int y) { Queue<Position> queue = new PriorityQueue<>(); queue.add(new Position(x, y, 0)); visited[x][y] = true; while (!queue.isEmpty()) { Position poll = queue.poll(); int pollX = poll.x; int pollY = poll.y; int pollTime = poll.time; if (pollX == N - 1 && pollY == N - 1) { min = min > pollTime ? pollTime : min; } for (int i = 0; i < 4; i++) { int ix = pollX + dx[i]; int iy = pollY + dy[i]; if (ix >= 0 && iy >= 0 && ix < N && iy < N) { if (!visited[ix][iy]) { int totalTime = pollTime + map[ix][iy]; queue.add(new Position(ix, iy, totalTime)); visited[ix][iy] = true; } } } } } static class Position implements Comparable<Position> { int x; int y; int time; Position(int x, int y, int time) { this.x = x; this.y = y; this.time = time; } @Override public int compareTo(Position o) { if (this.time < o.time) { return -1; } else if (this.time > o.time) { return 1; } return 0; } } }
'알고리즘 문제 풀이' 카테고리의 다른 글
[백준] 5568 카드 놓기 - Java (0) 2024.05.22 [백준] 11047 동전 0 - Java (0) 2024.05.21 [백준] 1697 숨바꼭질 - Java (0) 2024.05.15 [백준] 7576 토마토 - Java (0) 2024.05.15 [백준] 2178 미로 탐색 - Java (0) 2024.05.14