SWEA 1249 보급로 JAVA

문제 링크

SWEA 보급로
D4
그래프 탐색

풀이

가중치가 다른 그래프이므로 다익스트라를 사용하는게 가장 효율적이겠지만 다익스트라 알고리즘에 대해 잘 모르고 dfs나 bfs로도 가능할 것같은데 라는 생각이들어서 dfs로 도전했다.
오랜시간 동안 삽질을 하다가 다른 블로그를 참고해봤지만 나와 다른 부분이 어떤 부분인지 오래도록 찾지못했고 결국은 상하좌우 격자 탐색을 할 때 순서에따라 실행시간이 다르다는것을 알게되었다.

1. DFS로 푸는방법

1. 문제에서는 시작지점이 무조건 (0,0)으로 정해져있으므로 오른쪽탐색과 아래탐색이 우선순위가 높아야 더 빠른시간내에 탐색을 끝낼수 있는것 같았다.

2. 그리고 dfs 도중에 가지치기를 해주어야 하는데, 지금까지 도착점까지의 최단거리(ans)보다 지금 현재 진행하고있는 경로의 거리 (sum[x][y])가 더 크다면 더 탐색해볼 가치가 없으므로 return 해주어서 다른 경로를 찾아봐야한다. 그리고 다음 좌표의 공사시간과 지금까지의 공사시간의 sum값을 더한값(tmp)이 기존에 저장된 다음 좌표의 공사시간의 sum값보다 크면 더이상 탐색할 가치가 없으므로 탐색을 진행하지 않는다.

1-(1) Scanner +System.out 으로 입력 출력 받기

=> 약 1.7초

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

public class swea1249 {

    static int N,ans;
    static int dir[][] = new int[][] {{0,1},{1,0},{-1,0},{0,-1}};

    static boolean[][] visited;
    static int[][] sum;
    static int [][] arr;
    static Scanner scanner=new Scanner(System.in);
    public static void main(String[] args) throws  IOException {
        // TODO Auto-generated method stub
         
            int T = scanner.nextInt();
            for (int o = 1; o <= T; o++) {
                ans=Integer.MAX_VALUE;
                N=scanner.nextInt();
                arr=new int[N][N];
                visited= new boolean[N][N];
                sum=new int[N][N];
                for(int i=0;i<N;i++) {
                    Arrays.fill(sum[i], Integer.MAX_VALUE);
                }
                
                
                for(int i=0;i<N;i++) {
                   String str=scanner.next();
                    for(int j=0;j<N;j++) {
                        arr[i][j]=str.charAt(j)-'0';
                    }
                }
                sum[0][0]=0;
                visited[0][0]=true;
                dfs(0,0);
                
                System.out.println("#" + o + " " + ans);

                
                
            }
    }
    public static void dfs(int x, int y) {
        if(x==N-1&&y==N-1) {
            ans=Math.min(ans,sum[x][y]);
            return;
        }
        if(ans<=sum[x][y]) return;
        for(int a=0;a<4;a++) {
            int nx=x+dir[a][0];
            int ny=y+dir[a][1];
            if(nx>=0&&ny>=0&&nx<N&&ny<N) {
                int tmp=sum[x][y]+arr[nx][ny];
                if(!visited[nx][ny]||tmp<sum[nx][ny]) {        
                    visited[x][y]=true;
                    sum[nx][ny]=tmp;
                    dfs(nx,ny);

               }
            }
        }
        
       
    }

}

1-(2) BufferedReader 와 StringBuilder로 입출력

=> 약 1.4초

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

public class swea1249 {

    static int N,ans;
    static int dir[][] = new int[][] {{0,1},{1,0},{-1,0},{0,-1}};

    static boolean[][] visited;
    static int[][] sum;
    static int [][] arr;
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb=new StringBuilder();

    public static void main(String[] args) throws  IOException {
        // TODO Auto-generated method stub
             long start=System.currentTimeMillis();
            int T = Integer.parseInt(br.readLine());
            for (int o = 1; o <= T; o++) {
                ans=Integer.MAX_VALUE;
                N=Integer.parseInt(br.readLine());
                arr=new int[N][N];
                visited= new boolean[N][N];
                sum=new int[N][N];
                for(int i=0;i<N;i++) {
                    Arrays.fill(sum[i], Integer.MAX_VALUE);
                }
                
                
                for(int i=0;i<N;i++) {
                    char[] str=br.readLine().toCharArray();
                    for(int j=0;j<N;j++) {
                        arr[i][j]=str[j]-'0';
                    }
                }
                sum[0][0]=0;
                visited[0][0]=true;
                dfs(0,0);
                
                sb.append("#" + o + " " + ans+"\n");

                
                
            }
            System.out.println(sb);
            System.out.println(System.currentTimeMillis()-start);
    }
    public static void dfs(int x, int y) {
        if(x==N-1&&y==N-1) {
            ans=Math.min(ans,sum[x][y]);
            return;
        }
        if(ans<=sum[x][y]) return;
        for(int a=0;a<4;a++) {
            int nx=x+dir[a][0];
            int ny=y+dir[a][1];
            if(nx>=0&&ny>=0&&nx<N&&ny<N) {
                int tmp=sum[x][y]+arr[nx][ny];
                if(!visited[nx][ny]||tmp<sum[nx][ny]) {        
                    visited[x][y]=true;
                    sum[nx][ny]=tmp;
                    dfs(nx,ny);

               }
            }
        }
        
       
    }

}

1-(3) 1-(2)에서 격자 탐색 순서를 위 왼쪽 아래 오른쪽 순으로 바꿨을 때

=> 약 15초 (swea에서는 시간초과)
답은 나오나 시간초과

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

public class swea1249 {

    static int N,ans;
    static int dir[][] = new int[][] {{1,0},{0,-1},{-1,0},{0,1}};

    static boolean[][] visited;
    static int[][] sum;
    static int [][] arr;
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb=new StringBuilder();

    public static void main(String[] args) throws  IOException {
        // TODO Auto-generated method stub
             long start=System.currentTimeMillis();
            int T = Integer.parseInt(br.readLine());
            for (int o = 1; o <= T; o++) {
                ans=Integer.MAX_VALUE;
                N=Integer.parseInt(br.readLine());
                arr=new int[N][N];
                visited= new boolean[N][N];
                sum=new int[N][N];
                for(int i=0;i<N;i++) {
                    Arrays.fill(sum[i], Integer.MAX_VALUE);
                }
                
                
                for(int i=0;i<N;i++) {
                    char[] str=br.readLine().toCharArray();
                    for(int j=0;j<N;j++) {
                        arr[i][j]=str[j]-'0';
                    }
                }
                sum[0][0]=0;
                visited[0][0]=true;
                dfs(0,0);
                
                sb.append("#" + o + " " + ans+"\n");

                
                
            }
            System.out.println(sb);
            System.out.println(System.currentTimeMillis()-start);
    }
    public static void dfs(int x, int y) {
        if(x==N-1&&y==N-1) {
            ans=Math.min(ans,sum[x][y]);
            return;
        }
        if(ans<=sum[x][y]) return;
        for(int a=0;a<4;a++) {
            int nx=x+dir[a][0];
            int ny=y+dir[a][1];
            if(nx>=0&&ny>=0&&nx<N&&ny<N) {
                int tmp=sum[x][y]+arr[nx][ny];
                if(!visited[nx][ny]||tmp<sum[nx][ny]) {        
                    visited[x][y]=true;
                    sum[nx][ny]=tmp;
                    dfs(nx,ny);

               }
            }
        }
        
       
    }

}

2.BFS로 푸는법

visited를 체크하지않고 다음 공사시간과 지금까지의 최소값을 더한것이 지금까지의 nxny의 최소값보다 작을 때만 탐색을 진행한다.
bfs의 경우 상하좌우 순서를 맞춰주지 않아도 시간초과가 뜨지 않는다.
=> 약 0.4초

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class swea1249_bfs {
    public static class position2{
        int x,y;
        position2(int x, int y){
            this.x=x;
            this.y=y;
        }
    }
    static int N,ans;
    static int dir[][] = new int[][] {{1,0},{0,-1},{-1,0},{0,1}};

    static boolean[][] visited;
    static int[][] sum;
    static int [][] arr;
    static Scanner scanner=new Scanner(System.in);
    public static void main(String[] args) {
        long start=System.currentTimeMillis();

        // TODO Auto-generated method stub
        int T = scanner.nextInt();
        for (int o = 1; o <= T; o++) {
            ans=Integer.MAX_VALUE;
            N=scanner.nextInt();
            arr=new int[N][N];
            visited= new boolean[N][N];
            sum=new int[N][N];
            for(int i=0;i<N;i++) {
                Arrays.fill(sum[i], Integer.MAX_VALUE);
            }
            
            
            for(int i=0;i<N;i++) {
                String str =scanner.next();
                for(int j=0;j<N;j++) {
                    arr[i][j]=str.charAt(j)-'0';
                }
            }
            sum[0][0]=0;
            
            bfs(0,0);
            System.out.println("#" + o + " " + sum[N-1][N-1]);
            
        }
        System.out.println(System.currentTimeMillis()-start);

    }
    public static void bfs(int x,int y) {
        Queue <position2> q= new LinkedList<>();
        q.offer(new position2(x, y));
        while(!q.isEmpty()) {
            position2 next=q.poll();
            for(int i=0;i<4;i++) {
                int nx=next.x+dir[i][0];
                int ny=next.y+dir[i][1];
                
                if(nx>=0&&ny>=0&&nx<N&&ny<N) {
                    if(sum[nx][ny]>arr[nx][ny]+sum[next.x][next.y]) {
                        sum[nx][ny]=arr[nx][ny]+sum[next.x][next.y];
                        q.offer(new position2(nx, ny));
                    }
                }
            }
        }
     }

3. 다익스트라로 푸는법

bfs가 O(V+E)의 시간복잡도를 가지는 반면에 다익스트라는 O(ElogV)의 시간 복잡도를 가진다. 위에서 bfs로 푸는 방법이 1. 방문하지 않은 노드 중 가장 비용이 적은 노드를 선택한다. (그리디)
2. 해당 노드로 부터 갈 수 있는 노드들의 비용을 갱신한다.(dp) 다익스트라 매커니즘과 같다. 이번에는 우선순위 큐를 사용하여 최적화 해보도록 했다.
기본 로직은 위와같다.
=> 약 0.3 초

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;


public class swea1249_dijkstra {

    public static class Info implements Comparable<Info>{
        int x,y; 
        int distance;  //인덱스와 가중치를 저장한다.
        Info(int x,int y, int distance){ 
            this.x=x;
            this.y=y;
            this.distance=distance;
        }
        public int compareTo(Info other) {  //가중치를 기준으로 comparable을 선언하여 우선순위 큐의 판단 기준을 제공한다.
            if(this.distance<other.distance) {//비교할 값보다 지금이 최소값일 때 -> 교환안함
                return -1;      //음수 일경우 : 교환안함
            }
            return 1;
        }
    }
    static int N,ans;
    static int dir[][] = new int[][] {{0,1},{1,0},{-1,0},{0,-1} };

    static boolean[][] visited;
    static int[][] sum;
    static int [][] arr;
    static Scanner scanner=new Scanner(System.in);
    public static void main(String[] args) {
        long start=System.currentTimeMillis();

        int T = scanner.nextInt();
        for (int o = 1; o <= T; o++) {
            ans=Integer.MAX_VALUE;
            N=scanner.nextInt();
            arr=new int[N][N];
            visited= new boolean[N][N];
            sum=new int[N][N];
            for(int i=0;i<N;i++) {
                Arrays.fill(sum[i], Integer.MAX_VALUE);
            }
            sum[0][0]=0;
            
            for(int i=0;i<N;i++) {
                String str =scanner.next();
                for(int j=0;j<N;j++) {
                    arr[i][j]=str.charAt(j)-'0';
                }
            }
            
            dijkstra();
            System.out.println("#" + o + " " + sum[N-1][N-1]);

    }
        System.out.println(System.currentTimeMillis()-start);

    }
    public static void dijkstra() {
        PriorityQueue<Info> pq =new PriorityQueue<>();
        pq.offer(new Info(0,0,0));
        
        while(!pq.isEmpty()) {
            Info cur=pq.poll();
            if(cur.distance>sum[cur.x][cur.y])continue;      
            
            for(int i=0;i<4;i++) {
                int nx=cur.x+dir[i][0];
                int ny=cur.y+dir[i][1];
                
                if(nx>=0&&ny>=0&&nx<N&&ny<N) {
                    int nd=cur.distance+arr[nx][ny];
                    if(sum[nx][ny]>nd) {
                        sum[nx][ny]=nd;
                        pq.offer(new Info(nx, ny, sum[nx][ny]));
                    }
                }
            }
        }
        
    }
}