SWEA 1249 보급로

전재우·2021년 4월 12일
0

문제 정리

  1. 출발지에서 도착지까지 가는 경로 중에 도로 복구를 하려고 한다.
  2. 출발지에서 도착지까지 가는 경로 중에 복구 시간이 가장 짧은 경로에 대한 총 복구시간을 구하여라.
  3. 도로가 파여진 깊이에 비례해서 복구 시간은 증가한다.
  4. 깊이가 1이면 복구에 드는 시간은 1이다.
  5. 지도 정보는 2차원 배열 형태로 주어진다.
  6. 출발지: 좌상단, 도착지: 우하단
  7. 상하좌우 방향으로 한 칸씩 움직일 수 있다.

구현 전 생각

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));
				}
			}
		}
		
	}
}
profile
코린이

0개의 댓글