[삼성 SW Expert Academy] 보급로 SW1249 [JAVA]

Problem

※ SW Expert Academy는 문제의 무단 복제를 금지하고 있기 때문에, 기재하지 못한 점 양해 부탁드립니다.

Link

※ 하단의 Link를 클릭해도, 로그인 후 열람이 가능합니다.

풀이 방법

1. 출발지 부터 목적지 까지 가중치가 가장 작은 곳으로 도달하기 

2. 그 때의 가장 작은 총 복구시간을 구하는 것과 같다.

3. 따라서, 다익스트라 문제이다.

4. 다익스트라 연습하기 좋은 문제이다.

   (1) queue 사용하지 않고 풀기
   (2) queue 만 사용하고 풀기
   (3) PriorityQueue 사용해서 편하게 풀기 

3 가지 다 해보면 다익스트라에 대한 이해가 깊어 질 것이다.

(1) 코드는 짰는데, 날라가서 그냥 글로만 남긴다.

 로직 -> while(true) 반복문 안에서
  1) 방문하지 않은 노드 중 가장 작은 가중치 가지고 있는 위치 꺼내기 O(n^2)
   1-1) 그 곳이 목적지라면 종료 ! 
  2) 방문처리
  3) 해당 노드로부터 4방 탐색하며, 거리값 갱신이 가능하면 갱신해주고, 그렇지 않다면 패스 ! 

(2) queue 만 사용하고 풀기

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.Scanner;
import java.util.StringTokenizer;

public class 보급로_SW1249 {

	static int Tc, INF=Integer.MAX_VALUE;
	static int N;
	static int[][] map;
	static int[][] dist;
	static int[] dr = {-1, 0, 1, 0};
	static int[] dc = { 0, 1, 0, -1};
	
	private static class Road {
		int r;
		int c;
		int depth;
		private Road( int r, int c ,int depth) {
			this.r = r;
			this.c = c;
			this.depth = depth;
		}
		
	}
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Scanner sc = new Scanner(System.in);
		StringTokenizer st;
		
		Tc = sc.nextInt();
		
		for( int tc=1; tc<=Tc; tc++) {
			
			N =sc.nextInt();
			
			map = new int[N][N];
			dist = new int[N][N];
			
			for( int i=0; i<N; i++) {
				String input = sc.next(); 
				for( int j=0; j<N;j ++) {
					map[i][j] = input.charAt(j) - '0';
				}
			} // input 
			
			
			// initial
			for( int i=0; i<N; i++) {
				Arrays.fill(dist[i], INF);
			}
			
			
			dijkstra(0,0, N-1,N-1);
			
			
			System.out.println("#"+tc+" "+dist[N-1][N-1]);
		}
		
	}
	private static void dijkstra(int startX, int startY, int endX, int endY) {
		
		Queue<Road> road = new LinkedList<>();
		
		road.add(new Road(startX, startY, 0));
		dist[startX][startY] = 0;
		
		while( !road.isEmpty()) {
			
			Road Cur = road.poll();

			int r= Cur.r;
			int c= Cur.c;
			int PresentDepth = Cur.depth;
			// 이곳이 목적지라면 ? 
			if ( r == endX && c == endY	) {
				return;
			}
			
			// 4방향 돌면서 
			for( int d=0; d<4; d++) {
				
				int nr = r + dr[d];
				int nc = c + dc[d];
				
				if ( !IsIn(nr,nc) ) continue;
				
				// 기존 거리 값보다 , 거쳐서 통과하는 곳의 시간이 더 조금 걸린다면, 업데이트 해주고 큐에 넣어주자
				if ( PresentDepth + map[nr][nc] < dist[nr][nc] ) {
					dist[nr][nc] = PresentDepth + map[nr][nc];
					road.add( new Road(nr,nc, dist[nr][nc]));
				}
				
			}
		}
		
		
	}
	
	private static boolean IsIn(int r, int c ) {
		
		if ( r>=0 && r<N && c>=0 && c<N) return true;
		return false;
	}
	
	
	private static void print() {
		
		for( int i=0; i<N; i++) {
			for( int j=0; j<N; j++) {
				System.out.print(map[i][j]+" ");
			}
			System.out.println();
		}
		
	}

}

  (3) PriorityQueue 사용해서 편하게 풀기 - 큐처럼 사용하되, visit 처리만 해주면된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class 보급로_우선순위큐 {

	static int Tc, INF=Integer.MAX_VALUE;
	static int N;
	static int[][] map;
	static int[][] dist;
	static int[] dr = {-1, 0, 1, 0};
	static int[] dc = { 0, 1, 0, -1};
	static boolean[][] visited ;
	static int answer ;
	private static class Road implements Comparable<Road>{
		int r;
		int c;
		int depth;
		private Road( int r, int c ,int depth) {
			this.r = r;
			this.c = c;
			this.depth = depth;
		}
		
		@Override
		public int compareTo(Road o) {
			return this.depth - o.depth;
		}
		
	}
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Scanner sc = new Scanner(System.in);
		StringTokenizer st;
		
		Tc = sc.nextInt();
		
		for( int tc=1; tc<=Tc; tc++) {
			
			N =sc.nextInt();
			
			map = new int[N][N];
			dist = new int[N][N];
			visited = new boolean[N][N];
			
			
			for( int i=0; i<N; i++) {
				String input = sc.next(); 
				for( int j=0; j<N;j ++) {
					map[i][j] = input.charAt(j) - '0';
				}
			} // input 
			
			
			// initial
			for( int i=0; i<N; i++) {
				Arrays.fill(dist[i], INF);
			}
			answer = Integer.MAX_VALUE;
			
			
			dijkstra(0,0, N-1,N-1);
			
			
			System.out.println("#"+tc+" "+answer);
		}
		
	}
	private static void dijkstra(int startX, int startY, int endX, int endY) {
		
		PriorityQueue<Road> pq = new PriorityQueue<>();
		pq.add(new Road(startX, startY, 0));
		dist[startX][startY] = 0;
		visited[startX][startY] = true;
		while( !pq.isEmpty()) {
			
			Road Cur = pq.poll();

			int r= Cur.r;
			int c= Cur.c;
			int PresentDepth = Cur.depth;
			// 이곳이 목적지라면 ? 
			if ( r == endX && c == endY	) {
				answer = PresentDepth;
				return;
			}
			
			// 4방향 돌면서 
			for( int d=0; d<4; d++) {
				
				int nr = r + dr[d];
				int nc = c + dc[d];
				
				if ( !IsIn(nr,nc) ) continue;
				
				// 기존 거리 값보다 , 거쳐서 통과하는 곳의 시간이 더 조금 걸린다면, 업데이트 해주고 큐에 넣어주자
				if ( !visited[nr][nc]) {
					visited[nr][nc] = true;
					pq.add( new Road(nr,nc, PresentDepth + map[nr][nc])) ;
				}
				
			}
		}
		
		
	}
	
	private static boolean IsIn(int r, int c ) {
		
		if ( r>=0 && r<N && c>=0 && c<N) return true;
		return false;
	}
	
	
	private static void print() {
		
		for( int i=0; i<N; i++) {
			for( int j=0; j<N; j++) {
				System.out.print(map[i][j]+" ");
			}
			System.out.println();
		}
		
	}

}