다익스트라 > 1504번 / DFS와 BFS > 14502번

1504번

 

 

INF의 값을 INTEGER.MAX_VALUE로 설정할 경우 더하는 과정에서 오버플로우가 발생하므로 주의해야 한다

 

// 정점의 개수 = n
// 간선의 개수 = e
// 1번 정점에서 n번 정점으로 최단 거리로 이동 (시작점 1)
// 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동 가능
// 주어진 두 정점(v1, v2)을 반드시 거치면서 최단 경로로 이동
// (1번 > v1) + (v1 > v2) + (v2 > n번)
// (1번 > v2) + (v2 > v1) + (v1 > n번)
// 두 가지 경우를 모두 고려한 후 그 중 작은 값이 정답
// 경로가 없을 때에는 -1을 출력


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

// 정수의 오버플로우에 조심하자!

public class baekjoon1504 {

    static int n;
    static int e;
    static ArrayList <Route> [] lists;
    static int [] result;
    static boolean[] visited;
    static int INF = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());

        lists = new ArrayList[n+1];

        for(int i = 1; i<n+1; i++) {
            lists[i] = new ArrayList<>();
        }

        for(int i = 0; i<e; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            lists[a].add(new Route(b, value)); // 양방향
            lists[b].add(new Route(a, value));
        }

        st = new StringTokenizer(br.readLine(), " ");
        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());

        // 오버플로우가 발생할 수 있어 한 번에 더할 수 없다

        long answer1 = 0;  // 1->v1->v2->n
        answer1 += 다익스트라(1, v1);
        answer1 += 다익스트라(v1, v2);
        answer1 += 다익스트라(v2, n);
        long answer2 = 0; // 1->v2->v1->n
        answer2 += 다익스트라(1, v2);
        answer2 += 다익스트라(v2, v1);
        answer2 += 다익스트라(v1, n);
        if (Math.min(answer1, answer2) >= INF) {
            System.out.println(-1);
            return;
        }
        System.out.println(Math.min(answer1, answer2));
    }

    public static int 다익스트라 (int x, int y) {
        result = new int[n+1];
        visited = new boolean[n+1];
        Arrays.fill(result, INF);
        PriorityQueue <Route> queue = new PriorityQueue<>();
        queue.offer(new Route(x, 0));
        result[x] = 0;
        while (!queue.isEmpty()) {
            Route route = queue.poll();
            if(!visited[route.num]) {
                visited[route.num] = true;
                for(Route next : lists[route.num]) {
                    if(result[next.num] > result[route.num] + next.distance) {
                        result[next.num] = result[route.num] + next.distance;
                        queue.offer(new Route(next.num, result[next.num]));
                    }
                }
            }
        }
        return result[y];
    }
}

class Route implements Comparable <Route>{
    int num;
    int distance;
    Route (int num, int distance) {
        this.num = num;
        this.distance = distance;
    }

    @Override
    public int compareTo(Route o) {
        return this.distance-o.distance;
    }
}

 

INF의 값의 범위를 줄일 경우 정수의 오버플로우가 발생하지 않는다

경로의 최대 길이로 INF를 설정할 경우 INF + INF + INF가 int의 범위를 벗어나지 않는다

 

// 거리 최댓값 = 1000, 간선 개수 최댓값 = 200000 > 경로의 최대 길이 = 200000000

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static int n;
    static int e;
    static ArrayList <Route> [] lists;
    static int [] result;
    static boolean[] visited;
    static int INF = 200000000;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());

        lists = new ArrayList[n+1];

        for(int i = 1; i<n+1; i++) {
            lists[i] = new ArrayList<>();
        }

        for(int i = 0; i<e; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            lists[a].add(new Route(b, value)); // 양방향
            lists[b].add(new Route(a, value));
        }

        st = new StringTokenizer(br.readLine(), " ");
        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());
        int ans1= 다익스트라(1, v1)+다익스트라(v1, v2)+다익스트라(v2, n);
        int ans2= 다익스트라(1, v2)+다익스트라(v2, v1)+다익스트라(v1, n);
        if(ans1 >= INF && ans2 >=INF) {
            System.out.println(-1);
        } else {
            System.out.println(Math.min(ans1, ans2));
        }
    }

    public static int 다익스트라 (int x, int y) {
        result = new int[n+1];
        visited = new boolean[n+1];
        Arrays.fill(result, INF);
        PriorityQueue <Route> queue = new PriorityQueue<>();
        queue.offer(new Route(x, 0));
        result[x] = 0;
        while (!queue.isEmpty()) {
            Route route = queue.poll();
            if(!visited[route.num]) {
                visited[route.num] = true;
                for(Route next : lists[route.num]) {
                    if(result[next.num] > result[route.num] + next.distance) {
                        result[next.num] = result[route.num] + next.distance;
                        queue.offer(new Route(next.num, result[next.num]));
                    }
                }
            }
        }
        return result[y];
    }
}

class Route implements Comparable <Route>{
    int num;
    int distance;
    Route (int num, int distance) {
        this.num = num;
        this.distance = distance;
    }

    @Override
    public int compareTo(Route o) {
        return this.distance-o.distance;
    }
}

 

14502번

 

 

// 바이러스는 상하좌우 빈 칸으로 퍼짐
// 0 = 빈 칸, 1 = 벽, 2 = 바이러스
// 새로 세울 수 있는 벽의 개수 = 3

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class baekjoon14502 {

    static int n;
    static int m;
    static int [][] graph; // 연구소 상태를 나타내는 이차원 배열
    static int [][] graphCopy;
    static int[] dx = {-1, 1, 0, 0}; // 행
    static int[] dy = {0, 0, -1, 1}; // 열
    static int result = Integer.MIN_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        graph = new int[n+1][m+1];
        for(int i = 1; i<n+1; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 1; j<m+1; j++) {
                int num = Integer.parseInt(st.nextToken());
                graph[i][j] = num;
            }
        }
        makeWall(0);
        System.out.println(result);
    }

    // 연구소 모든 칸을 확인하면서 빈 칸이 있다면 벽을 세운다
    public static void makeWall (int count) {
        if(count == 3) { // 벽은 3개만 만들 수 있으므로
            bfs(); // 바이러스 확산 시작
            return;
        }
        for(int i = 1; i<n+1; i++) {
            for(int j = 1; j<m+1; j++) {
                if(graph[i][j] == 0) {
                    graph[i][j] = 1;
                    makeWall(count+1);
                    graph[i][j] = 0; // 다시 원상복구
                }
            }
        }
    }

    public static void bfs () {
        graphCopy = new int[n+1][m+1]; // 기존 연구소 상태 배열을 바꾸면 안됨
        for(int i = 1; i<n+1; i++) {
            for(int j = 1; j<m+1; j++) {
                graphCopy[i][j]  = graph[i][j]; // 연구소 상태를 복사한 이차원 배열
            }
        }
        Queue<Virus> queue = new LinkedList<>();
        for(int i = 1; i<n+1; i++) {
            for(int j = 1; j<m+1; j++) {
                if(graph[i][j] == 2) {
                    queue.offer(new Virus(i, j)); // 바이러스가 있는 칸을 큐에 넣는다
                }
            }
        }
        while(!queue.isEmpty()) {
            Virus virus = queue.poll();
            for(int i = 0; i<dx.length; i++) { // 상하좌우 탐색
                int xx = virus.x + dx[i];
                int yy = virus.y + dy[i];
                if(check(xx, yy)) {
                    queue.offer(new Virus(xx, yy));
                    graphCopy[xx][yy] = 2;
                }
            }
        }
        virusCheck(graphCopy);
    }

    public static boolean check (int x, int y) {
        if (x < 1 || x > n || y < 1 || y > m) { // 연구소 내부를 벗어나지 않고
            return false;
        }
        if(graphCopy[x][y] != 0) { // 바이러스가 퍼지지 않은 칸
            return false;
        }
        return true;
    }

    // 바이러스가 퍼지지 않은 안전한 칸 확인 (칸의 값이 0인 경우)
    public static void virusCheck (int [][] graph) {
        int count = 0;
        for(int i = 1; i<n+1; i++) {
            for(int j = 1; j<m+1; j++) {
                if(graph[i][j] == 0) {
                    count++;
                }
            }
        }
        if(count > result) { // 최댓값 구하기
            result = count;
        }
    }
}

class Virus {
    int x;
    int y;
    Virus (int x, int y) {
        this.x = x;
        this.y = y;
    }
}