SWEA 1249 보급로
문제 정리
- 출발지에서 도착지까지 가는 경로 중에 도로 복구를 하려고 한다.
- 출발지에서 도착지까지 가는 경로 중에 복구 시간이 가장 짧은 경로에 대한 총 복구시간을 구하여라.
- 도로가 파여진 깊이에 비례해서 복구 시간은 증가한다.
- 깊이가 1이면 복구에 드는 시간은 1이다.
- 지도 정보는 2차원 배열 형태로 주어진다.
- 출발지: 좌상단, 도착지: 우하단
- 상하좌우 방향으로 한 칸씩 움직일 수 있다.
구현 전 생각
bfs를 이용해서 탐색을 구현
아쉬운점
bfs를 이용해서 최단 경로를 찾는 방법을 알게 된 좋은 문제 였다.
코드
package backjoon_4월;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import org.omg.CosNaming.IstringHelper;
public class SWEA_1249_보급로 {
static int map[][];
static int dx[] = {0,0,-1,1};
static int dy[] = {1,-1,0,0};
static int ans[][];
static int N;
static int min =Integer.MAX_VALUE;
static class point{
int x,y;
public point(int x, int y) {
super();
this.x = x;
this.y = y;
}
}
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int TC = Integer.parseInt(br.readLine());
for (int t = 1; t <= TC; t++) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
map = new int[N][N];
ans = new int[N][N];
min=Integer.MAX_VALUE;
for(int i=0; i<N; i++) {
Arrays.fill(ans[i], Integer.MAX_VALUE);
}
ans[0][0] = 0;
for(int i=0; i<N; i++){
String[] temp = br.readLine().split("");
for(int j=0; j<N; j++){
map[i][j] = Integer.parseInt(temp[j]);
}
}
bfs();
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < N; j++) {
//
// System.out.print(ans[i][j]+" ");
// }
// System.out.println();
// }
System.out.println("#"+t+" "+min);
}
}
public static void bfs() {
Queue<point> que = new LinkedList<point>();
boolean isSelected[][] = new boolean[N][N];
que.add(new point(0,0));
isSelected[0][0]=true;
while(!que.isEmpty()) {
point cur = que.poll();
if(cur.x==N-1 && cur.y==N-1) {
min= min > ans[N-1][N-1] ? ans[N-1][N-1] : min;
}
if(min <= ans[cur.x][cur.y])
continue;
for (int i = 0; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if(nx<0||ny<0||nx>=N||ny>=N) continue;
//if(isSelected[nx][ny]) continue;
if(!isSelected[nx][ny]||ans[nx][ny] > ans[cur.x][cur.y] + map[nx][ny]) {
isSelected[nx][ny]=true;
ans[nx][ny] = ans[cur.x][cur.y] + map[nx][ny];
que.add(new point(nx,ny));
}
}
}
}
}
Author And Source
이 문제에 관하여(SWEA 1249 보급로), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jeus95/SWEA-1249-보급로저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)