풀이
최단 경로를 묻는 bfs 문제입니다
map에는 루피값을 넣어주고
check에 해당 경로까지 최솟값을 갱신해주면서 bfs를 풀었습니다.
아래처럼 방문한 적이 있든 없든, check에 해당 경로까지 최솟 값이 있으므로
조건을 줘서 다음경로까지의 거리합 > 현재 경로까지의 거리합 + 다음 경로 거리값 이면
큐에 넣어줬습니다.
if(check[nx][ny]>check[x][y]+map[nx][ny]) {
check[nx][ny]=check[x][y]+map[nx][ny];
queue.offer(new int[] {nx,ny});
}
import java.io.*;
import java.util.*;
// bfs문제 check 현재 위치를 도달할 수 있는 최솟값을 갱신하면서 탐색
public class Main {
static int[][] map, check;
static Queue<int[]> queue = new LinkedList<int[]>();
static int[] dx= {1,0,-1,0};
static int[] dy= {0,1,0,-1};
static int n;
public static void main(String[] args) throws Exception{
// TODO Auto-generated method stub
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st ;
int tc=1;
while(true) {
n=Integer.parseInt(br.readLine());
map=new int[n][n];
check=new int[n][n];
if(n!=0) {
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());
check[i][j]=987654321;
}
}
bfs(0,0);
System.out.println("Problem "+ tc++ +": "+check[n-1][n-1]);
}
else {
break;
}
}
br.close();
}
private static void bfs(int a, int b) {
// TODO Auto-generated method stub
check[a][b]=map[a][b];
queue.offer(new int[] {a,b});
while(! queue.isEmpty()) {
int[] cur=queue.poll();
int x=cur[0];
int y=cur[1];
for(int i=0; i<4; i++) {
int nx= cur[0] + dx[i];
int ny= cur[1] + dy[i];
if(0<=nx && nx<n && 0<=ny && ny<n) {
// check에 현재까지 온 거리합 갱신
if(check[nx][ny]>check[x][y]+map[nx][ny]) {
check[nx][ny]=check[x][y]+map[nx][ny];
queue.offer(new int[] {nx,ny});
}
}
}
}
}
}
'알고리즘 > 문제 풀이' 카테고리의 다른 글
[Java/자바 swea 5643] 키 순서 (0) | 2021.09.30 |
---|---|
[Java/자바 swea 8458] 원점으로 집합 (0) | 2021.09.29 |
[JAVA/자바 정올 1681] 해밀턴 순환회로 (0) | 2021.09.24 |
[JAVA/자바 백준 17472] 다리 만들기2 (0) | 2021.09.17 |
[JAVA/자바 백준 14502] 연구소 (0) | 2021.09.17 |