View
λ°μν
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD
package SWEA;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
public class Solution_1249 {
static int map[][];
static int N, res;
static int[] dx = { -1, 1, 0, 0 };
static int[] dy = { 0, 0, 1, -1 };
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int t = 1; t < T + 1; t++) {
N = Integer.parseInt(br.readLine());
map = new int[N][N];
for (int i = 0; i < N; i++) {
String s = br.readLine();
for (int j = 0; j < N; j++) {
map[i][j] = s.charAt(j) - '0';
}
}
res = 0;
bfs();
System.out.println("#" + t + " " + res);
}
}
private static void bfs() {
// μ°μ μμ ν μ¬μ©
PriorityQueue<Node> que = new PriorityQueue<>();
boolean visit[][] = new boolean[N][N];
visit[0][0] = true;
que.add(new Node(0, 0, map[0][0]));
while (!que.isEmpty()) {
// Iterator iterator = que.iterator();
// while (iterator.hasNext())
// System.out.println(iterator.next() + " ");
Node node = que.poll();
if (node.x == N - 1 && node.y == N - 1) {
res = node.time;
return;
}
for (int i = 0; i < 4; i++) {
int nx = dx[i] + node.x;
int ny = dy[i] + node.y;
// 첫 λΉκ΅λμ μ΄κΈ°ν
if (nx >= 0 && ny >= 0 && nx < N && ny < N && visit[ny][nx] != true) {
// μκ° κ°±μ ν΄μ μ°μ μμ νμ λ£μ
int totalTime = node.time + map[ny][nx];
que.add(new Node(ny, nx, totalTime));
visit[ny][nx] = true;
}
}
}
}
static public class Node implements Comparable<Node> {
int x, y, time;
public Node(int y, int x, int time) {
this.y = y;
this.x = x;
this.time = time;
}
@Override
// 볡ꡬμκ°μ΄ μμμλ‘ -> μ€λ¦μ°¨μ μ λ ¬
public int compareTo(Node o) {
return this.time - o.time;
}
@Override
public String toString() {
return "Node [x=" + x + ", y=" + y + ", time=" + time + "]";
}
}
}
bfsλ§ μ¨μ νλΌκ³ νλλ° μ½κ² λ λ¦¬κ° μμ§,,
μ°μ μμ νλ₯Ό μ¬μ©νκ±°λ νΉμ dp+bfsλ‘ νΈλ λ°©λ²μ΄ μλλ―
λλ μ°μ μμ νλ₯Ό μ¬μ©ν΄μ timeμ΄ μ κ² κ±Έλ¦¬λ μμΌλ‘ μ€λ¦μ°¨μ μν΄
λ°μν
'μκ³ λ¦¬μ¦ > μ½λ©ν μ€νΈ' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[λ°±μ€] 10814: λμ΄μ μ λ ¬(Java) (0) | 2022.10.03 |
---|---|
[λ°±μ€_μ€ν¨] (0) | 2022.10.02 |
[νλ‘κ·Έλλ¨Έμ€] μμ£Όνμ§ λͺ»ν μ μ(Java) (0) | 2022.10.01 |
[λ°±μ€] 2879: μνμμ (Java) (0) | 2022.10.01 |
[μ½λ©ν μ€νΈ] μ½ν λλΉ λ¬Έμ μΆμ² (0) | 2022.10.01 |
reply