SWEA 1238 - 보급로
Updated:
Java
1238 번 - 보급로
문제
BC의 정보와 사용자의 이동 궤적이 주어졌을 때, 모든 사용자가 충전한 양의 합의 최댓값을 구하는 프로그램을 작성하라.
접근 방법
최단 경로를 구하는 문제였다.
따라서, 최단 경로를 구하는 알고리즘인 다익스트라, 그리고 BFS를 사용하여 해결하였다.
다익스트라의 경우, (1,1)에서 (n,n)으로 가는 최단 경로를 구하는데,
2차원 배열을 통하여 방문 여부와 각 노드 까지 도달하는데 걸리는 시간을 나타내었다.
처음 (1,1)은 시작점이므로, 비용이 0으로 시작하며
n x n의 모든 노드 중, 방문하지 않았고 가장 비용이 적은 노드부터 선택한다.
한 노드에서 다른 노드로 갈 수 있는 방법은 [상,하,좌,우] 이므로, 현재 노드에서 4방향으로 탐색한다.
현재 노드까지 도달한 cost와 다음 노드로 가는 비용을 합한 것이, 이전에 기록한 다음 노드까지 걸리는 비용보다 저렴하다면, 더 낮은 cost로 갱신을 한다.
위 과정을 반복하면, 노드 (n,n)값 1,1 에서 n,n까지 가는데 최소의 비용이 들어있다.
BFS의 경우
가중치가 다 같은 경우에는, bfs로 문제를 해결 할 시 목표 지점에 도달하는 그 상황이 가장 최단 거리가 된다.
하지만 이 문제와 같이 가중치가 다 다른 경우, 이전에 한번 도달하였다 해도 다음에 도달하는 경우에 비용이 더 작을 수도 있다.
따라서 한번 방문 하였다 해도, 다음에 도달하는 경우 비용이 더 작다면 그 비용을 현재 노드의 값으로 갱신하고 노드의 정보를 queue에 넘어 다시 탐색하도록 한다.
코드 - BFS
import java.io.*;
import java.util.*;
class Solution {
static int result = 0;
static int[][] map;
static int[][] ans;
static boolean[][] vis;
static int[] dy = {-1,1,0,0};
static int[] dx = {0,0,-1,1};
static int n;
public static void main(String []args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk;
int tc = stoi(br.readLine());
for(int tidx = 1; tidx <= tc; tidx++) {
result = 0;
n = stoi(br.readLine());
map = new int[n][n];
ans = new int[n][n];
vis = new boolean[n][n];
String str;
for(int i = 0; i < n; i++) {
str = br.readLine();
for(int j = 0; j < n; j++) {
map[i][j] = str.charAt(j) - '0';
}
}
for(int i = 0; i < n; i++) {
Arrays.fill(ans[i], Integer.MAX_VALUE);
}
ans[0][0] = 0;
BFS();
result = ans[n-1][n-1];
System.out.println("#" + tidx + " " + result);
}
}
static void BFS() {
Queue<int[]> queue = new LinkedList<int[]>();
queue.add(new int[] {0,0});
vis[0][0] = true;
int[] temp;
int y,x,ny,nx;
while(!queue.isEmpty()) {
temp = queue.poll();
y = temp[0];
x = temp[1];
for(int i = 0; i < 4; i++) {
ny = y + dy[i];
nx = x + dx[i];
if(!isIn(ny,nx)) {
continue;
}
if(!vis[ny][nx] || ans[ny][nx] > map[ny][nx] + ans[y][x]) {
vis[ny][nx] = true;
ans[ny][nx] = map[ny][nx] + ans[y][x];
queue.add(new int[] {ny,nx});
}
}
}
}
// 주어진 범위 안에 있는가
public static boolean isIn(int y, int x){
if(y < 0 || y >= n || x < 0 || x >= n)
return false;
return true;
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}
코드 - 다익스트라
import java.io.*;
import java.util.*;
class Solution {
static int result = 0;
static int[][] map;
static boolean[][] vis;
static int[] dy = {-1,1,0,0};
static int[] dx = {0,0,-1,1};
static int n;
public static void main(String []args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk;
int tc = stoi(br.readLine());
for(int tidx = 1; tidx <= tc; tidx++) {
result = 0;
n = stoi(br.readLine());
map = new int[n][n];
vis = new boolean[n][n];
String str;
for(int i = 0; i < n; i++) {
str = br.readLine();
for(int j = 0; j < n; j++) {
map[i][j] = str.charAt(j) - '0';
}
}
System.out.println("#" + tidx + " " + dijkstra(0, 0));
}
}
static int dijkstra(int startR, int startC) {
int[][] minTime = new int[n][n];
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
minTime[i][j] = Integer.MAX_VALUE;
}
}
minTime[startR][startC] = 0;
int r = 0, c = 0, cost = 0, nr, nc;
while(true) {
// 방문하지 않은 정점 중 출발지에서 자신으로 오는 비용이 최소인 정점 선택
cost = Integer.MAX_VALUE;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(!vis[i][j] && cost > minTime[i][j]) {
cost = minTime[i][j];
r = i;
c = j;
}
}
}
vis[r][c] = true;
// 선택된 정점을 기준으로 [인접한 정점 중에] 방문하지 않은 나머지 정점들 자신과의 경유시의 비용과 기존 최소 비용 비교하여 최소값 업데이트
if(r == n-1 && c == n-1) {
return cost;
}
for(int d = 0; d < 4; d++) {
nr = r + dy[d];
nc = c + dx[d];
if(isIn(nr,nc) && !vis[nr][nc] && minTime[nr][nc] > cost + map[nr][nc]) {
minTime[nr][nc] = cost + map[nr][nc];
}
}
}
}
// 주어진 범위 안에 있는가
public static boolean isIn(int y, int x){
if(y < 0 || y >= n || x < 0 || x >= n)
return false;
return true;
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}
코드 - 다익스트라 + PQ
import java.io.*;
import java.util.*;
class Solution {
static int result = 0;
static int[][] map;
static boolean[][] vis;
static int[] dy = {-1,1,0,0};
static int[] dx = {0,0,-1,1};
static int n;
public static void main(String []args) throws Exception {
System.setIn(new FileInputStream("res/input.txt")); //제출 할 때 주석해야함
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk;
int tc = stoi(br.readLine());
for(int tidx = 1; tidx <= tc; tidx++) {
result = 0;
n = stoi(br.readLine());
map = new int[n][n];
vis = new boolean[n][n];
String str;
for(int i = 0; i < n; i++) {
str = br.readLine();
for(int j = 0; j < n; j++) {
map[i][j] = str.charAt(j) - '0';
}
}
System.out.println("#" + tidx + " " + dijkstra(0, 0));
}
}
static int dijkstra(int startR, int startC) {
int[][] minTime = new int[n][n];
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
minTime[i][j] = Integer.MAX_VALUE;
}
}
// 정점 r : [0] || c : [1] || 출발지로부터 복구시간 : [2]
PriorityQueue<int[]> queue = new PriorityQueue<>((o1,o2)->{return Integer.compare(o1[2], o2[2]);});
minTime[startR][startC] = 0;
queue.offer(new int[] {startR,startC,0});
int[] current;
int r = 0, c = 0, cost = 0, nr, nc;
while(true) {
// 방문하지 않은 정점 중 출발지에서 자신으로 오는 비용이 최소인 정점 선택
current = queue.poll();
r = current[0];
c = current[1];
cost = current[2];
if(vis[r][c])
continue;
vis[r][c] = true;
// 선택된 정점을 기준으로 [인접한 정점 중에] 방문하지 않은 나머지 정점들 자신과의 경유시의 비용과 기존 최소 비용 비교하여 최소값 업데이트
if(r == n-1 && c == n-1) {
return cost;
}
for(int d = 0; d < 4; d++) {
nr = r + dy[d];
nc = c + dx[d];
if(isIn(nr,nc) && !vis[nr][nc] && minTime[nr][nc] > cost + map[nr][nc]) {
minTime[nr][nc] = cost + map[nr][nc];
queue.offer(new int[] {nr, nc, minTime[nr][nc]});
}
}
}
}
// 주어진 범위 안에 있는가
public static boolean isIn(int y, int x){
if(y < 0 || y >= n || x < 0 || x >= n)
return false;
return true;
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}
총평
후기
개선할 점
없
