Life Engineering
[BOJ 4485] 녹색 옷 입은 애가 젤다지? (Java) 본문
https://www.acmicpc.net/problem/4485
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main_BOJ_4485 {
static class Node implements Comparable<Node>{
int r, c, cost;
public Node(int r, int c, int cost) {
super();
this.r = r;
this.c = c;
this.cost = cost;
}
@Override
public int compareTo(Node o) {
return this.cost-o.cost;
}
}
static int[] dr= {-1,1,0,0};
static int[] dc= {0,0,-1,1};
static int N;
static int[][] map;
static int[][] dist;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=null;
int problem=1;
while (true) {
N=Integer.parseInt(br.readLine());
if (N==0) break;
map=new int[N][N];
dist=new int[N][N];
for (int i=0; i<N; i++) {
st=new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j]=Integer.parseInt(st.nextToken());
dist[i][j]=Integer.MAX_VALUE;
}
}
StringBuilder sb=new StringBuilder("Problem ");
sb.append(problem); sb.append(": "+bfs());
System.out.println(sb.toString());
problem++;
}
}
private static int bfs() {
PriorityQueue<Node> q=new PriorityQueue<>();
q.add(new Node(0,0,map[0][0]));
dist[0][0]=map[0][0];
while (!q.isEmpty()) {
Node curr=q.poll();
int r=curr.r;
int c=curr.c;
int cost=curr.cost;
for (int i=0; i<4; i++) {
int nr=r+dr[i];
int nc=c+dc[i];
if (nr<0 || nc<0 || nr>=N || nc>=N) continue;
if (dist[nr][nc]>cost+map[nr][nc]) {
dist[nr][nc]=cost+map[nr][nc];
q.add(new Node(nr, nc, dist[nr][nc]));
}
}
}
return dist[N-1][N-1];
}
}
다익스트라 느낌의 BFS 문제.
주변 4방향을 탐색해가면서 기존 거리보다 작은 거리로 도착이 가능할 경우, 그 값을 갱신해주고 그 노드를 탐색 대상으로 집어넣는다.
'Problem Solving' 카테고리의 다른 글
[BOJ 20057] 마법사 상어와 토네이도 (Java) (0) | 2022.04.01 |
---|---|
[BOJ 1194] 달이 차오른다, 가자. (Java) (0) | 2022.04.01 |
[BOJ 1062] 가르침 (Java) (0) | 2022.03.31 |
[BOJ 1600] 말이 되고픈 원숭이 (Java) (0) | 2022.03.30 |
[BOJ 20055] 컨베이어 벨트 위의 로봇 (Java) (0) | 2022.03.30 |