문제 링크
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD
# 문제 풀이
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;
}
}
}
'알고리즘' 카테고리의 다른 글
[백준][Java] 숨바꼭질 3 (0) | 2023.05.31 |
---|---|
[SWEA][Java] 탈주범 검거 (0) | 2023.05.25 |
[SWEA][Java] 수영장 (0) | 2023.05.22 |
[SWEA][Java] 프로세서 연결하기 (0) | 2023.05.21 |
[java][백준 11066] 파일 합치기 (0) | 2023.04.01 |