새소식

인기 검색어

알고리즘 문제풀이/SWEA

[SWEA] 1249번 보급로 자바(java) 풀이 (bfs)

  • -

sw expert academy 1249번 보급로 자바(java) 풀이

문제 정리

  1. 출발지에서 도착지까지 가는 경로 중에 도로 복구를 하려고 한다.
  2. 출발지에서 도착지까지 가는 경로 중에 복구 시간이 가장 짧은 경로에 대한 총 복구시간을 구하여라.
  3. 도로가 파여진 깊이에 비례해서 복구 시간은 증가한다.
  4. 깊이가 1이면 복구에 드는 시간은 1이다.
  5. 지도 정보는 2차원 배열 형태로 주어진다.
  6. 출발지: 좌상단, 도착지: 우하단
  7. 상하좌우 방향으로 한 칸씩 움직일 수 있다.


문제 접근

간단합니다. bfs로 모든 경우를 탐색합니다. 그 위치에서의 최대값을 갱신해나갑니다. 우하단의 값을 가지고 최소값을 update해나가면 됩니다. 이 외에 다른 방법으로도 풀어 보았습니다.

  1. bfs
  2. bfs(우선 순위 큐)
  3. dfs
  4. 다익스트라


bfs (Solution.java)

bfs를 구현하기 위해서 queue를 사용하였습니다.
4번에서 방문하였더라도 그 길로 오는 것이 복구시간이 더 작은 경우 update 해주고 그 길로 이동하도록 하여야 합니다.

  1. 시작 위치를 방문했다고 check하고 queue에 넣습니다.
  2. 위, 아래, 왼쪽, 오른쪽으로 모두 이동합니다.
    이 때 isValidPosition을 통해 이동 가능한 경우만 queue에 넣을 수 있도록 합니다.
  3. 이동 가능하고 방문하지 않았고 이 길로 가는 것이 더 적은 시간이 걸린다면 queue에 넣고 방문 처리합니다.
    그리고 현 위치에서의 값에 이동할 위치의 복구시간을 더해서 update해줍니다.
    ex) 0,0에서 1,0으로 이동가능. 이 경우 1,0까지 오는데 필요한 복구시간은 ans[0][0] + map[1][0] = 3
    현 위치까지 오는데의 복구시간(ans[a][b])에 다음 이동할 위치의 복구시간(map[dx][dy])가 다른 경로로 왔을때의 복구시간(ans[dx][dy])보다 작으면 이 길로 가는 것이 더 복구시간이 더 적다는 뜻이됩니다.
  4. 위와 같은 과정을 우 하단에 도착할때 까지 반복하여 최소 값을 갱신해 나갑니다.
    이럻게 하면 우 하단에 오기까지 모든 경우중 가장 작은 값을 구할 수 있습니다.


bsf 우선순위 큐 이용(Solution2.java)

일반 큐 대신 우선순위 큐를 이용하여 시간이 덜 걸리는 곳 먼저 꺼내서 탐색 합니다.
우선 순위 큐는 다음과 같이 선언합니다.

import java.util.PriorityQueue;
PriorityQueue<Pos> q = new PriorityQueue<>();

그리고 큐에 담는 Pos 객체의 Comparable을 구현해야 합니다. 시간이 작은 것을 먼저 빼야 하기 때문에 오름차순 정렬합니다.

class Pos implements Comparable<Pos>{
    int x;
    int y;
    int time;

    Pos(int x, int y, int time){
        this.x = x;
        this.y = y;
        this.time = time;
    }

    // 오름차순 정렬
    @Override
    public int compareTo(Pos p){
        if(this.time > p.time)
            return 1;
        else if(this.time < p.time)
            return -1;
        return 0;
    }
}



dfs (Solution3.java)

이러한 문제 유형은 bfs로 푸는것이 맞습니다. 하지만 dfs에 가지치기를 잘 하면 dfs로 문제를 통과할 수 있습니다. 로직은 bfs와 같습니다.

  1. ans 배열에 현재 그 위치까지 오는데 걸리는 최소 시간을 저장해 갑니다.
  2. 만약 이동하려는 위치의 ans값이 min보다 작으면 탐색하지 않습니다.
  3. 또한 이동하려는 위치의 ans값(ans[dx][dy])이 현재까지 오는데 필요한 시간(ans[a][b]) 에 이동하려는 칸에서 걸리는 시간을 더한 것 보다 크면 최소가 될 수 없기에 이동할 필요가 없으므로 큐에 담지 않습니다. 
    if(!visited[dx][dy] || ans[dx][dy] > ans[a][b] + map[dx][dy]){
 visited[dx][dy] = true;
 ans[dx][dy] = ans[a][b] + map[dx][dy];
 stack.push(new Pos(dx, dy));
}


dijkstra(다익스트라) 알고리즘 이용(Solution4.java)

정점 A에서 정점 B까지 최단 경로를 찾는 문제와 같기 때문에 다익스트라 알고리즘을 이용하여 풀 수도 있습니다.
0. 거리를 저장할 distance 2차원 배열(int)을 모두 MAX 값으로 초기화 합니다. 방문 여부를 저장할 visited 2차원 배열(boolean)도 필요합니다.

  1. 시작 노드를 초기화 합니다. (distance=0, 방문 체크)
  2. 시작 노드와 연결된 노드의 distance를 갱신해 줍니다.
  3. distance중 최소값을 가지는 index를 찾습니다.(minX, minY)
  4. 최소 거리를 가지는 정점을 방문처리 합니다.
  5. 방금 방문한 정점과 연결되었으며 방문하지 않은 노드들에 대해 더 짧은 거리가 있다면 갱신합니다.
  6. 3-5번은 모든 점에 대하여 check 합니다.(시작, 끝 점 제외 n*n-2개)


swea 보급로 bfs 자바 코드(Solution.java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
class Pos {
int x;
int y;
Pos(int x, int y){
this.x = x;
this.y = y;
}
}
class Solution {
// 위, 아래, 왼쪽, 오른쪽
static int[] xdir = {-1,1,0,0};
static int[] ydir = {0,0,-1,1};
static int n;
static int[][] map;
static int min;
static boolean[][] visited;
static int[][] ans;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int testNum = Integer.parseInt(br.readLine());
for(int test=1; test<=testNum; test++){
n = Integer.parseInt(br.readLine());
map = new int[n][n];
// map 입력받기
for(int i=0; i<n; i++){
String[] temp = br.readLine().split("");
for(int j=0; j<n; j++){
map[i][j] = Integer.parseInt(temp[j]);
}
}
min = Integer.MAX_VALUE;
visited = new boolean[n][n];
ans = new int[n][n];
for(int i=0; i<n; i++)
Arrays.fill(ans[i], Integer.MAX_VALUE);
ans[0][0] = 0;
bfs(0,0);
System.out.println("#" + test + " " + min);
}
br.close();
}
private static void bfs(int x, int y){
Queue<Pos> q = new LinkedList<>();
q.offer(new Pos(x,y));
visited[x][y] = true;
while(!q.isEmpty()){
Pos p = q.poll();
int a = p.x;
int b = p.y;
// 우 하단 도착지에 도착한 경우
// 최소값과 비교하여 더 작다면 갱신한다.
if(a == n-1 && b == n-1)
min = min > ans[n-1][n-1] ? ans[n-1][n-1] : min;
// 가지치기
if(min <= ans[a][b])
continue;
for(int i=0; i<4; i++){
int dx = a + xdir[i];
int dy = b + ydir[i];
if(isValidPosition(dx, dy)){
if(!visited[dx][dy] || ans[dx][dy] > ans[a][b] + map[dx][dy]){
visited[dx][dy] = true;
ans[dx][dy] = ans[a][b] + map[dx][dy];
q.offer(new Pos(dx, dy));
}
}
}
}
}
private static boolean isValidPosition(int x, int y){
if(x < 0 || x >= n || y < 0 || y >= n)
return false;
return true;
}
}
view raw swea1249_1.java hosted with ❤ by GitHub



swea 보급로 우선순위 큐 이용 bfs 자바 코드(Solution2.java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
class Pos implements Comparable<Pos>{
int x;
int y;
int time;
Pos(int x, int y, int time){
this.x = x;
this.y = y;
this.time = time;
}
// 오름차순 정렬
@Override
public int compareTo(Pos p){
if(this.time > p.time)
return 1;
else if(this.time < p.time)
return -1;
return 0;
}
}
class Solution2 {
// 위, 아래, 왼쪽, 오른쪽
static int[] xdir = {-1,1,0,0};
static int[] ydir = {0,0,-1,1};
static int n;
static int[][] map;
static int min;
static boolean[][] visited;
static int[][] ans;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int testNum = Integer.parseInt(br.readLine());
for(int test=1; test<=testNum; test++){
n = Integer.parseInt(br.readLine());
map = new int[n][n];
// map 입력받기
for(int i=0; i<n; i++){
String[] temp = br.readLine().split("");
for(int j=0; j<n; j++){
map[i][j] = Integer.parseInt(temp[j]);
}
}
min = Integer.MAX_VALUE;
visited = new boolean[n][n];
ans = new int[n][n];
for(int i=0; i<n; i++)
Arrays.fill(ans[i], Integer.MAX_VALUE);
ans[0][0] = 0;
bfs(0,0);
System.out.println("#" + test + " " + min);
}
br.close();
}
private static void bfs(int x, int y){
PriorityQueue<Pos> q = new PriorityQueue<>();
q.offer(new Pos(x,y,0));
visited[x][y] = true;
while(!q.isEmpty()){
Pos p = q.poll();
int a = p.x;
int b = p.y;
int time = p.time;
// 우 하단 도착지에 도착한 경우
// 최소값과 비교하여 더 작다면 갱신한다.
if(a == n-1 && b == n-1)
min = min > time ? time : min;
// 가지치기
if(min <= time)
continue;
for(int i=0; i<4; i++){
int dx = a + xdir[i];
int dy = b + ydir[i];
if(isValidPosition(dx, dy)){
int dtime = time + map[dx][dy];
if(!visited[dx][dy] || dtime < ans[dx][dy]){
visited[dx][dy] = true;
ans[dx][dy] = dtime;
q.offer(new Pos(dx, dy, dtime));
}
}
}
}
}
private static boolean isValidPosition(int x, int y){
if(x < 0 || x >= n || y < 0 || y >= n)
return false;
return true;
}
}
view raw swea1249_2.java hosted with ❤ by GitHub



swea 보급로 dfs 자바 코드(Solution3.java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.Arrays;
class Pos {
int x;
int y;
Pos(int x, int y){
this.x = x;
this.y = y;
}
}
class Solution3 {
// 위, 아래, 왼쪽, 오른쪽
static int[] xdir = {-1,1,0,0};
static int[] ydir = {0,0,-1,1};
static int n;
static int[][] map;
static int min;
static boolean[][] visited;
static int[][] ans;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int testNum = Integer.parseInt(br.readLine());
for(int test=1; test<=testNum; test++){
n = Integer.parseInt(br.readLine());
map = new int[n][n];
// map 입력받기
for(int i=0; i<n; i++){
String[] temp = br.readLine().split("");
for(int j=0; j<n; j++){
map[i][j] = Integer.parseInt(temp[j]);
}
}
min = Integer.MAX_VALUE;
visited = new boolean[n][n];
ans = new int[n][n];
for(int i=0; i<n; i++)
Arrays.fill(ans[i], Integer.MAX_VALUE);
ans[0][0] = 0;
dfs(0,0);
System.out.println("#" + test + " " + min);
}
br.close();
}
private static void dfs(int x, int y){
Stack<Pos> stack = new Stack<>();
stack.push(new Pos(x,y));
visited[x][y] = true;
while(!stack.isEmpty()){
Pos p = stack.pop();
int a = p.x;
int b = p.y;
// 우 하단 도착지에 도착한 경우
// 최소값과 비교하여 더 작다면 갱신한다.
if(a == n-1 && b == n-1)
min = min > ans[n-1][n-1] ? ans[n-1][n-1] : min;
// 가지치기
if(min <= ans[a][b])
continue;
for(int i=0; i<4; i++){
int dx = a + xdir[i];
int dy = b + ydir[i];
if(isValidPosition(dx, dy)){
if(!visited[dx][dy] || ans[dx][dy] > ans[a][b] + map[dx][dy]){
visited[dx][dy] = true;
ans[dx][dy] = ans[a][b] + map[dx][dy];
stack.push(new Pos(dx, dy));
}
}
}
}
}
private static boolean isValidPosition(int x, int y){
if(x < 0 || x >= n || y < 0 || y >= n)
return false;
return true;
}
}
view raw swea1249_3.java hosted with ❤ by GitHub



swea 보급로 다익스트라 자바 코드(Solution4.java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
class Solution4 {
// 위, 아래, 왼쪽, 오른쪽
static int[] xdir = {-1,1,0,0};
static int[] ydir = {0,0,-1,1};
static int n;
static int[][] map;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int testNum = Integer.parseInt(br.readLine());
for(int test=1; test<=testNum; test++){
n = Integer.parseInt(br.readLine());
map = new int[n][n];
// map 입력받기
for(int i=0; i<n; i++){
String[] temp = br.readLine().split("");
for(int j=0; j<n; j++){
map[i][j] = Integer.parseInt(temp[j]);
}
}
dijkstra(test,0,0);
}
br.close();
}
private static void dijkstra(int test, int x, int y){
boolean[][] visited;
int[][] distance;
visited = new boolean[n][n];
distance = new int[n][n];
// distance 초기화
for(int i=0; i<n; i++)
Arrays.fill(distance[i], Integer.MAX_VALUE);
// 시작 노드 초기화
distance[x][y] = 0;
visited[x][y] = true;
// 연결노드 distance 갱신
for(int i=0; i<4; i++){
int dx = x + xdir[i];
int dy = y + ydir[i];
if(isValidPosition(dx, dy) && !visited[dx][dy])
distance[dx][dy] = map[dx][dy];
}
// 모든 점 check
for(int a=0; a<n*n-2; a++){
int min = Integer.MAX_VALUE;
int minX = -1;
int minY = -1;
// 최소값 찾기
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(!visited[i][j] && distance[i][j] != Integer.MAX_VALUE){
if(distance[i][j] < min){
min = distance[i][j];
minX = i;
minY = j;
}
}
}
}
visited[minX][minY] = true;
// minX, minY와 연결되면서 방문하지 않은 노드들에 대해 check
for(int i=0; i<4; i++){
int dx = minX + xdir[i];
int dy = minY + ydir[i];
if(isValidPosition(dx, dy) && !visited[dx][dy]){
if(distance[dx][dy] > distance[minX][minY] + map[dx][dy]){
distance[dx][dy] = distance[minX][minY] + map[dx][dy];
}
}
}
}
System.out.println("#" + test + " " + distance[n-1][n-1]);
}
private static boolean isValidPosition(int x, int y){
if(x < 0 || x >= n || y < 0 || y >= n)
return false;
return true;
}
}
view raw swea1249_4.java hosted with ❤ by GitHub
Contents

당신이 좋아할만한 콘텐츠

댓글 0

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.

SHARE

DARK

MENU

티스토리툴바