[백준 9251/1520/9370] 자바

(title: [백준 9251/1520/9370] 자바)

A. LCS BOJ 9251

https://www.acmicpc.net/problem/9251

9251번: LCS

난이도	Gold 5
풀이 시간	10분
분류	DP
시간복잡도	O(NM)
공간복잡도

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;

        String str1 = br.readLine();
        String str2 = br.readLine();
        int n = str1.length();
        int m = str2.length();
        int[][] dp = new int[n + 1][m + 1];

        int max_length = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if(str1.charAt(i-1)==str2.charAt(j-1)){
                    // 같다면
                     dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    // 같지 않다면
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
                max_length = Math.max(dp[i][j], max_length);
            }
        }

        bw.write(max_length+"\n");
        bw.flush();
        bw.close();
    }

}

(추가)

위 문제는 LCS 의 길이를 구하는 문제이지만 만약 LCS 자체를 구해야 하는 경우에는 아래의 역추적 코드를 사용하면 된다.

Stack<Character> st = new Stack<>();
int now = 0;
int i = n;
int j = m;
while (i > 0 && j > 0) {
    if (i == 0 || j == 0)
        continue;
    now = dp[i][j];
    if (now == dp[i - 1][j]) {
        i--;
    } else if (now == dp[i][j - 1]) {
        j--;
    } else {
        st.add(str1.charAt(i - 1));
        i--;
        j--;
    }
}

bw.write(max_length + "\n");

while (!st.empty()){
    bw.append(st.pop());
} bw.newLine();

OUTPUT:

4
ACAK

 

B. 내리막길 BOJ 1520

https://www.acmicpc.net/problem/1520

1520번: 내리막 길

난이도	Gold 3
풀이 시간	50분
분류	DFS + DP, BFS with Priority Queue
시간복잡도	dfs : O(4V) ~= O(V) bfs : O(VlogV)
공간복잡도	O(V)

[1. DFS + DP 를 이용한 풀이]

static int dfs(int x, int y) {
    if (y == row - 1 && x == col - 1) {
        return 1;
    }
    if (dp[y][x] != -1) {
        return dp[y][x]; // 이미 저장된 값이 있을 시 그것을 반환
    }
    dp[y][x] = 0;
    for (int dir = 0; dir < 4; dir++) {
        int nx = x + dx[dir];
        int ny = y + dy[dir]; // 새로 이동할 좌표
        if (nx < 0 || nx >= col || ny < 0 || ny >= row) {
            continue; // out of bounds
        }
        if (graph[y][x] > graph[ny][nx]) {
            // 내리막 길이면
            dp[y][x] += dfs(nx, ny);
        }
    }
    return dp[y][x];
}

[2. BFS + Priority Queue 를 사용한 풀이]

static int bfs(int x, int y, int heigh) {
    dp[y][x] = 1;
    PriorityQueue<Node> pq = new PriorityQueue<>();
    pq.add(new Node(x, y, heigh));
    while (!pq.isEmpty()) {
        Node now = pq.poll();
        for (int dir = 0; dir < 4; dir++) {
            int nx = now.x + dx[dir];
            int ny = now.y + dy[dir];
            if (nx < 0 || nx >= col || ny < 0 || ny >= row) {
                continue; // out of bounds
            }
            if (graph[now.y][now.x] > graph[ny][nx]) {
                // 내리막 길이면
                if (dp[ny][nx]==0) {
                    pq.add(new Node(nx, ny, graph[ny][nx]));
                }
                dp[ny][nx] += dp[now.y][now.x];
            }

        }
    }
    return dp[row - 1][col - 1];
}

 

 

C. 미확인 도착지 BOJ 9370

https://www.acmicpc.net/problem/9370

9370번: 미확인 도착지

난이도	Gold 2
풀이 시간	40 분
분류	다익스트라
시간복잡도	우선순위 큐를 사용한 다익스트라 알고리즘의 시간 복잡도는 O((V+E)logV) 이다. 노드의 최대 개수는 2000 개이고 엣지의 최대 개수는 50000 개 그리고 테스트 케이스의 최대 개수는 100 개이다 그러면 최악의 경우에 시간 복잡도는 대략 (2000+50000)log2000 * 100 ~= 17,165,355 = 천칠백만번의 연산이 필요하다는 것을 알 수 있다. 일반적인 환경에서 2천만번의 연산을 1초 이내에 처리 가능하므로, 위 코드는 시간제한 3 초 안에 안전하게 수행될 것이라고 합리적으로 예상이 가능하다.
공간복잡도	O(n+m)

문제 설명이 조금 이해하기 어렵게 되어있는데, 간단하게 요약하면 이렇다.

 

주어지는 정보는 s(시작점), t0,t1,t2...(후보 목적지), g-h (목적지로 향할 때 반드시 거쳐야 하는 경로) 인데,

 

우리가 구해야 하는 것은 s 부터 g-h , h-g 를 거쳐서 후보 목적지인 t0, ... tn 에 도달하는 것이 최단 경로인 지 파악하는 것이다. 

 

즉, s 에서 출발하여 후보 목적지에 도달하는 최단 거리(1)와 s 에서 출발하고 g-h 혹은 h-g 를 거쳐서 후보 목적지에 도달하는 최단 거리(2)를 구한 다음 이를 비교하여 후보 목적지 중에서 가능하지 않은 것을 제외시켜주면 된다.

 

이러한 판단이 가능한 이유는 문제 상황에서 서커스 예술가 한 쌍은 반드시 최단 경로로만 이동한다는 가정 때문이다.

 

그리고 이들이 g 와 h 사이의 도로를 통과했다는 정보가 주어지므로, 

 

g 와 h 사이의 도로를 통과하지 않고 후보 목적지로 도달하는 방법이 최단 거리라면

 

후보 목적지에서 제외해도 된다는 것이다.

 

그러면 이를 어떻게 구현할까?

 

우리가 얻어야 하는 정보는 아래 두 가지 이다. 

 

1. s 부터 후보 목적지까지의 최단 거리

 

2. s 부터 g와 h 사이의 도로를 거쳐서 후보 목적지까지 도달하는 최단 거리

 

 

(2) 부터 생각해보자.s 에서 출발하여 g 와 h 사이의 도로를 거쳐서 후보 목적지(t) 까지 도달하는 경우는 아래 두 가지 케이스가 가능하다.s->g->h->ts->h->g->t그러므로 (2) = Math.min(s->g->h->t, s->h->g->t) 으로 구하면 될텐데, 

 

이를 위해서는 s->g 까지의 최단경로, g->h 까지의 최단경로, h->t 까지의 최단경로, s->h 까지의 최단경로, g->t 까지의 최단경로가 필요하다.

 

(1) 의 경우에는 s->t 까지의 최단경로가 필요하다.

 

즉, 3 가지 시작 노드(s, g, h)로 부터 모든 노드까지의 최단 거리를 계산할 수 있으면 우리가 얻고자 하는 정보를 모두 얻을수 있다.

 

3가지 단일 노드에 대한 전체 노드의 최단 거리를 계산하면 되는데, 이는 다익스트라 알고리즘의 시작점을 바꾸어 가면서 3번 수행하면 될 것임을 생각할 수 있다.

 

마침, 엣지의 가중치들은 모두 양수이므로  다익스트라 알고리즘을 수행할 수 있으며,

 

시간 복잡도 또한 널널하다.

 

우선순위 큐를 사용한 다익스트라 알고리즘의 시간 복잡도는 O((V+E)logV) 이다.
노드의 최대 개수는 2000 개이고
엣지의 최대 개수는 50000 개
그리고 테스트 케이스의 최대 개수는 100 개이다
그러면 최악의 경우에 시간 복잡도는 대략
(2000+50000)log2000 * 100 ~= 17,165,355 = 천칠백만번의 연산이 필요하다는 것을 알 수 있다.
일반적인 환경에서 2천만번의 연산을 1초 이내에 처리 가능하므로,
위 코드는 시간제한 3초 안에 안전하게 수행될 것이라고 합리적으로 예상이 가능하다.

 

그러므로 다익스트라의 시작점을 s, g, h 로 바꾸어 가면서 3 번 수행하며

 

 s->g 까지의 최단경로, g->h 까지의 최단경로, h->t 까지의 최단경로, s->h 까지의 최단경로, g->t 까지의 최단경로를 얻어내고,

 

이로부터 

 

1. s 부터 후보 목적지까지의 최단 거리

 

2. s 부터 g와 h 사이의 도로를 거쳐서 후보 목적지까지 도달하는 최단 거리

 

를 도출한 다음

 

g 와 h 사이의 도로를 통과하지 않고 후보 목적지로 도달하는 방법(1)이

g 와 h 사이의 도로를 통과하고 후보 목적지로 도달하는 방법(2) 보다 최단 거리라면 후보 목적지에서 제외시켜준다.

 

(왜냐면 무조건 g-h 를 통과해서 최단 경로로 진행한다는 전제가 주어졌는데, 계산 해보니 g-h 를 통과하는 방법이 최단 경로가 아니라면 후보 목적지가 아니기 때문이다.)

 

이렇게 하면 AC 를 받을 수 있다.

 

import java.io.*;
import java.util.*;

public class Main {
    static int n;
    static int m;
    static int t;
    static int s;
    static int g;
    static int h;
    static ArrayList<Node>[] graph;
    static int[] dist;

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;

        int tc = Integer.parseInt(br.readLine());
        while (tc > 0) {
            tc--;
            ArrayList<Integer> anslist = new ArrayList<>();
            stk = new StringTokenizer(br.readLine());
            n = Integer.parseInt(stk.nextToken()); // 노드 개수
            m = Integer.parseInt(stk.nextToken()); // 엣지 개수
            t = Integer.parseInt(stk.nextToken()); // 후보 개수

            stk = new StringTokenizer(br.readLine());
            s = Integer.parseInt(stk.nextToken()); // 시작점
            g = Integer.parseInt(stk.nextToken());
            h = Integer.parseInt(stk.nextToken());

            init();

            for (int i = 0; i < m; i++) {
                stk = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(stk.nextToken());
                int b = Integer.parseInt(stk.nextToken());
                int d = Integer.parseInt(stk.nextToken());
                graph[a].add(new Node(b, d));
                graph[b].add(new Node(a, d)); // 양방향
            }
            int minimum_path = Integer.MAX_VALUE;
            for (int i = 0; i < t; i++) {
                int dest = Integer.parseInt(br.readLine());
                dijkstra(s);
                int s2dest = dist[dest];
                int s2g = dist[g];
                int s2h = dist[h];
                dijkstra(g);
                int g2dest = dist[dest];
                int g2h = dist[h];
                dijkstra(h);
                int h2dest = dist[dest];

                int inf = Integer.MAX_VALUE;
                if (s2dest == inf || s2g == inf || s2h == inf || g2h == inf)
                    continue;
                int s2g2h2dest = s2g + g2h + h2dest;
                int s2h2g2dest = s2h + g2h + g2dest;
                minimum_path = Math.min(s2g2h2dest, s2h2g2dest);

                if(s2dest < minimum_path){
                    continue;
                } else {
                    anslist.add(dest);
                }
            }

            Collections.sort(anslist);
            for (Integer iter : anslist) {
                bw.write(iter + " ");
            }
            bw.newLine();
        }

        bw.flush();
        bw.close();
    }

    static class Node implements Comparable<Node> {
        int to;
        int w;

        public Node(int to, int w) {
            this.to = to;
            this.w = w;
        }

        @Override
        public int compareTo(Node o) {
            if (this.w > o.w)
                return 1;
            else return -1;
        }
    }

    static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        pq.add(new Node(start, 0));
        while (!pq.isEmpty()) {
            Node now = pq.poll();
            for (Node cur : graph[now.to]) {
                // 연결 노드 탐색
                if (dist[cur.to] > dist[now.to] + cur.w) {
                    dist[cur.to] = dist[now.to] + cur.w;
                    pq.add(new Node(cur.to, dist[cur.to]));
                }
            }
        }
    }

    static void init() {
        graph = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        dist = new int[n + 1];
    }
}