[SWEA][Java] 보급로

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD 

SW Expert Academy

 

# 문제 풀이

BFS

출발지에서 도착지까지의 최소 거리를 구하는 것이 아니라 최소 비용을 구하는 것이기 때문에 Node 클래스를 하나 만들어서 BFS를 다 돌리고 난 이후에 나온 값 중 가장 작은 값을 출력했습니다.

방문 처리와 최소비용을 같은 배열에서 처리했습니다. 이전 방문해서 나왔던 값보다 현재 방문해서 나온 값이 더 작은 경우에만 값을 업데이트하고 큐에 넣어줬습니다.

출발지와 도착지가 정해져 있기 때문에 BFS를 다 돌리고 결국 visited 배열의 도착지에 저장되어있는 값이 최소 비용입니다.

 

# 문제 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class SWEA보급로 {
	static int t, n, answer;
	static int[][] map, visited;
	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { -1, 1, 0, 0 };

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		t = Integer.parseInt(br.readLine());
		for (int tc = 1; tc < t + 1; tc++) {
			n = Integer.parseInt(br.readLine());
			map = new int[n][n];
			visited = new int[n][n];
			answer = Integer.MAX_VALUE;

			for (int i = 0; i < n; i++) {
				String[] s = br.readLine().split("");
				for (int j = 0; j < s.length; j++) {
					map[i][j] = Integer.parseInt(s[j]);
				}
				Arrays.fill(visited[i], -1);
			}

			bfs();
			sb.append("#" + tc + " " + visited[n - 1][n - 1] + "\n");
		}
		System.out.println(sb.toString());
	}

	private static void bfs() {
		Queue<Node> q = new LinkedList();
		q.add(new Node(0, 0, 0));
		visited[0][0] = -1;

		while (!q.isEmpty()) {
			Node node = q.poll();

			for (int i = 0; i < 4; i++) {
				int nx = node.x + dx[i];
				int ny = node.y + dy[i];

				if (nx < 0 || ny < 0 || nx >= n || ny >= n)
					continue;

				if (visited[ny][nx] == -1 || visited[ny][nx] > node.value + map[ny][nx]) {
					visited[ny][nx] = node.value + map[ny][nx];
					q.add(new Node(nx, ny, node.value + map[ny][nx]));
				}
			}
		}

	}

	public static class Node {
		int x, y, value;

		public Node(int x, int y, int value) {
			super();
			this.x = x;
			this.y = y;
			this.value = value;
		}
	}
}