[SWEA] 1249. 보급로 [Java]

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

 

 

 

 

 

처음에는 각 길의 최소 weight만을 저장하는 weight[][]를 선언해

 

모든곳을 bfs로 방문하여 weight의 최솟값을 계속해서 갱신해주게 되면

최종적으로 weight[N -1][N -1]가 경로의 최솟값이 되게끔 풀었다.

 

 

해결1. bfs로

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.concurrent.LinkedBlockingDeque;

class Solution {
	static int MIN;
	
	static int[][] weight;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int TC = Integer.parseInt(br.readLine());
		int[][] map;
		for (int k = 1; k <= TC; k++) {
			MIN = Integer.MAX_VALUE;
			int N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			
			weight = new int[N][N];
			for (int i = 0; i < N; i++) {
				String[] st = br.readLine().split("");
				for (int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(st[j]);
					
					weight[i][j] = Integer.MAX_VALUE;
				}
				
			}
			weight[0][0] = 0;
			bfs(map, N);
			System.out.println("#" +k + " "+ MIN);
		}

	}

	public static void bfs(int[][] map, int N) {
		Queue<Integer> xqueue = new LinkedList<>();
		Queue<Integer> yqueue = new LinkedList<>();
		xqueue.offer(0);
		yqueue.offer(0);

		while (!xqueue.isEmpty()) {
			int x = xqueue.poll();
			int y = yqueue.poll();
			
			if(x == N -1 && y == N - 1) {
				if(MIN > weight[x][y]) {
					MIN = weight[x][y];
				}
			}
			if (isValid(x, y + 1, N)) { // 오른쪽으로 갈 수 있으면
				if (weight[x][y] + map[x][y + 1] < weight[x][y + 1]) {
					weight[x][y + 1] = weight[x][y] + map[x][y + 1];
					if (weight[x][y + 1] < MIN) {
						xqueue.offer(x);
						yqueue.offer(y + 1);
					}
				}
			}
			if (isValid(x + 1, y, N) ) { // 아래 쪽으로 갈수 있으면
				if (weight[x][y] + map[x + 1][y] < weight[x + 1][y]) {
					weight[x + 1][y] = weight[x][y] + map[x + 1][y];
					if (weight[x + 1][y] < MIN) {
						xqueue.offer(x + 1);
						yqueue.offer(y);
					}
				}
			}
			if (isValid(x, y - 1, N)) { // 왼쪽으로 갈수 있으면
				if (weight[x][y] + map[x][y - 1] < weight[x][y - 1]) {
					weight[x][y - 1] = weight[x][y] + map[x][y - 1];
					if (weight[x][y - 1] < MIN) {
						xqueue.offer(x);
						yqueue.offer(y - 1);
					}
				}
			}
			if (isValid(x - 1, y, N) ) { // 위쪽으로 갈 수 있으면
				if (weight[x][y] + map[x - 1][y] < weight[x - 1][y]) {
					weight[x - 1][y] = weight[x][y] + map[x - 1][y];
					if (weight[x - 1][y] < MIN) {
						xqueue.offer(x - 1);
						yqueue.offer(y);
					}
				}
			}
			
		}
	}

	public static boolean isValid(int x, int y, int N) {
		return x >= 0 && x < N && y < N && y >= 0;
	}
}

weight[N-1][N-1]의 값을 MIN으로 두었고 점점 작은값으로 갱신해야나가니까

weight의 모든 요소는 Integer.MAX_VALUE 로 초기화해 주었다.

 

weight[x - 1][y] < MIN 일때만 큐에 offer를 하게 했는데
그 이유는 애초에 도착지점으로 가는 중간에 가중치가 MIN보다 커버린다면 그길은 탐색할 필요가 없어지기때문에

불필요한 탐색을 막는다.

 

 

 

 

 

 

 

해결2. 우선순위 큐로 bfs

import java.beans.Visibility;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.concurrent.LinkedBlockingDeque;

class Solution {
	static int MIN;
	static int[][] weight;
	static boolean[][] visited;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int TC = Integer.parseInt(br.readLine());
		int[][] map;
		for (int k = 1; k <= TC; k++) {
			MIN = Integer.MAX_VALUE;
			int N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			visited = new boolean[N][N];
			for (int i = 0; i < N; i++) {
				String[] st = br.readLine().split("");
				for (int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(st[j]);
					visited[i][j] = false;
				}
				
			}
			bfs(map, N);
			System.out.println("#" +k + " "+ MIN);
		}

	}

	public static void bfs(int[][] map, int N) {
		PriorityQueue<Path> queue = new PriorityQueue<>((a,b) -> a.weight.compareTo(b.weight));
		queue.offer(new Path(0,0,0));
		while(true) {
			Path p =queue.poll();
			visited[p.x][p.y] = true;
			
//			System.out.println(p);
			if(p.x == N -1  && p.y == N -1) {
				MIN = p.weight;
				break;
			}
			if(isValid(p.x, p.y + 1, N)) {
				queue.offer(new Path(p.x, p.y + 1,	p.weight + map[p.x][p.y + 1]));
			}
			if(isValid(p.x + 1, p.y, N)) {
				queue.offer(new Path(p.x + 1, p.y, p.weight + map[p.x + 1][p.y]));
				
			}
			if(isValid(p.x, p.y - 1, N)) {
				queue.offer(new Path(p.x, p.y - 1, p.weight + map[p.x][p.y - 1]));
				
			}
			if(isValid(p.x - 1, p.y, N)) {
				queue.offer(new Path(p.x - 1, p.y, p.weight + map[p.x - 1][p.y]));
				
			}
		}
		
	}

	public static boolean isValid(int x, int y, int N) {
		return x >= 0 && x < N && y < N && y >= 0 && !visited[x][y];
	}
}

class Path {
	int x;
	int y;
	Integer weight;
	
	Path(int x , int y , int w) {
		this.x = x;
		this.y = y;
		weight = w;
	}
	@Override
	public String toString () {
		return x + " ," + y +"(" + weight +")";  
	}
}

 

path의 정보를 저장하는 class Path를 선언했다.

이 클래스에는 x좌표 ,y좌표 그리고 현재까지 누적 가중치를 저장할수 있는 weight를 담았다.

만약 현재(0,0) -> (1,0) - > (2,0) 까지 갔다면

마지막 Path에는 x = 2 ,y = 0 ,weight =0,0 + 1,0 + 2,0을 합친 weight가 저장된다.

 

그리고 PriorityQueue에는 weight가 작은 순서대로 우선순위가 결정되게 선언한후,

bfs탐색을하면 끝 Path에 도달하는 순간 바로 그곳이 자동으로 최소경로가 된다.

 

 

성능차이는 둘다 250~230ms 사이로 성능은 비슷하다 하지만 

우선순위 큐를 쓴 코드가 더 간단하고 구현하기 쉽다.