[백준 13549/1956/1620/2629] 자바

(title: [백준 13549/1956/1620/2629] 자바)

A. 숨바꼭질3 BOJ 13549

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

13549번: 숨바꼭질 3

난이도	Gold 5
풀이 시간	20 분
분류	다익스트라 / 0-1 BFS
시간복잡도	다익스트라 : O(nlogn) 0-1 BFS : O(V+E) = O(N+N) ~= O(N)
공간복잡도

일차원 그래프에서 다익스트라 알고리즘을 수행하여 쉽게 해결할 수 있다.

다익스트라 알고리즘을 사용하는 이유는 문제 상황을 1차원 그래프로 바꾸어 생각해보면

모든 가중치는 1 또는 0 으로 양의 간선을 가지는 것을 알 수 있고,

다익스트라 알고리즘을 사용하면 O(nlogn) ~= 500000 이기 때문에 시간 제한에도 걸릴 염려가 없기 때문이다. 순간이동을 하는 경우에는 가중치가 0 인 노드를 우선순위 큐에 넣어주고, 걸어가는 경우에는 가중치가 1 인 노드를 우선순위 큐에 넣어주면 된다.

 

[다익스트라]

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

public class Main {

    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 v) {
            if (this.w > v.w)
                return 1;
            else return -1;
        }
    }

    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;

        stk = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(stk.nextToken());
        int k = Integer.parseInt(stk.nextToken());

        int[] dist = new int[100001];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[n] = 0;
        PriorityQueue<node> pq = new PriorityQueue<>();
        pq.add(new node(n, 0));


        while(!pq.isEmpty()){
            node now = pq.poll();
            node [] next = {
                    new node(now.to-1, 1),
                    new node(now.to+1, 1),
                    new node(now.to*2, 0)
            };
            for(node cur : next){
                if(cur.to<0||cur.to>100000) continue; // out of bounds
                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]));
                }
            }
        }

        bw.write(dist[k] + "\n");
        bw.flush();
        bw.close();
    }
}

혹은 0-1 BFS 알고리즘을 사용하면 보다 효율적일 여지가 있다. 0-1 BFS 는 0 또는 1 의 가중치만 가지는 그래프에서 최단경로를 찾아내는 알고리즘으로 dequeue 를 사용하여,  우선순위에 따라 앞에 add 할 지, 뒤에 add 할 지를 결정하면 된다. 이러한 0-1 BFS 알고리즘은 O(V+E) 의 시간복잡도를 가진다.

[0-1 BFS]

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

public class Main {

    static class node {
        int to;
        int w;

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

    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;

        stk = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(stk.nextToken());
        int k = Integer.parseInt(stk.nextToken());

        int[] dist = new int[100001];
        boolean[] visited = new boolean[100001];
        Arrays.fill(dist, -1);
        dist[n] = 0;
        visited[n] = true;
        LinkedList<node> dq = new LinkedList<>();
        dq.add(new node(n, 0));


        while (!dq.isEmpty()) {
            node now = dq.poll();
            node[] next = {
                    new node(now.to * 2, 0),
                    new node(now.to - 1, 1),
                    new node(now.to + 1, 1)
            };
            for (node cur : next) {
                if (cur.to < 0 || cur.to > 100000) continue; // out of bounds
                if (!visited[cur.to]) {
                    visited[cur.to] = true;
                    if (cur.w == 0) { // 순간이동
                        dist[cur.to] = dist[now.to];
                        dq.addFirst(new node(cur.to, cur.w));
                    } else { // 걸어감
                        dist[cur.to] = dist[now.to] + cur.w;
                        dq.addLast(new node(cur.to, cur.w));
                    }
                }
            }
        }

        bw.write(dist[k] + "\n");
        bw.flush();
        bw.close();
    }
}

 

 

B. 운동 BOJ 1956

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

1956번: 운동

난이도	Gold 4
풀이 시간	20 분
분류	플로이드 - 워셜
시간복잡도	O(V^3) ~= O(400^3) = O(64000000)
공간복잡도

  각각의 노드에서 도달할 수 있는 최단 경로 테이블이 있다면, 문제에서 정의하는 '사이클' 을 쉽게 판단할 수 있다. 예를 들어, a->b 로 가는 최단 경로가 존재한다면 b->a 로 가는 최단 경로가 존재하는 지 확인하고, 만약 존재한다면 그 둘의 최단 경로의 합이 사이클 거리가 될 것이다. 그 다음에는 a->c 로 가는 최단 경로가 존재한다면 c->a 로 가는 최단 경로가 존재하는 지 확인해보고 더 작은 값으로 계속 갱신해나가면 될 것 이다.

 

  즉, 모든 노드 간 최단 경로가 있으면 좋을텐데 문제의 제한 사항을 보니 노드의 개수는 최대 400 개 이다. 그러면, 모든 노드 간 최단 경로를 얻는 알고리즘인 플로이드-워셜 알고리즘을 수행하여도 시간 제한 내에 통과할 수 있을 것임을 알 수 있다.(O(V^3)) 

 

  그래프 거리 정보를 2차원 행렬에 받은 다음, 플루이드 워셜 알고리즘을 적용한다. 그리고 나서 A->B 까지의 최단 경로가 있다면 B->A 경로가 있는지 확인하고 있다면 이 두 경로의 합을 저장한다. 이러한 과정을 모든 노드에 대하여 반복하며 최단 사이클을 출력해주면 된다.

 

  조심해야 할 점은, 최단경로를 구하는 과정에서 오버플로우가 발생하여 우리가 원하지 않는 값으로 테이블이 채워질 수 있다는 것이다. 또 하나는, 주어진 그래프에서 사이클이 발생하지 않는 경우에는 -1 을 출력해야 한다는 것을 조심해야 한다.

 

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

public class Main {
    static int v;
    static int e;
    static long[][] 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;

        stk = new StringTokenizer(br.readLine());
        v = Integer.parseInt(stk.nextToken());
        e = Integer.parseInt(stk.nextToken());

        dist = new long[v + 1][v + 1];

        for (int i = 1; i <= v; i++) {
            for (int j = 1; j <= v; j++) {
                if (i == j)
                    dist[i][j] = 0;
                else
                    dist[i][j] = Integer.MAX_VALUE;
            }
        }

        for (int i = 0; i < e; i++) {
            stk = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(stk.nextToken());
            int b = Integer.parseInt(stk.nextToken());
            int cost = Integer.parseInt(stk.nextToken());
            dist[a][b] = cost;
        }

        for (int k = 1; k <= v; k++) {
            for (int st = 1; st <= v; st++) {
                for (int end = 1; end <= v; end++) {
                    if (dist[st][end] > dist[st][k] + dist[k][end]) {
                        dist[st][end] = dist[st][k] + dist[k][end];
                    }
                }
            }
        }

        long min = Integer.MAX_VALUE;
        for (int i = 1; i <= v; i++) {
            for (int j = 1; j <= v; j++) {
                 if(i==j) continue;
                 if(dist[i][j] != Integer.MAX_VALUE && dist[j][i] != Integer.MAX_VALUE){
                     min = Math.min(dist[i][j] + dist[j][i] ,min);
                 }
            }
        }

        if(min==Integer.MAX_VALUE){
            bw.write("-1\n");
        } else {
            bw.write(min+"\n");
        }

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

 

 

C. 나는야 포켓몬 마스터 이다솜 BOJ 1620

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

1620번: 나는야 포켓몬 마스터 이다솜

난이도	Silver 4
풀이 시간	10분
분류	해쉬맵
시간복잡도
공간복잡도

해쉬맵을 사용할 줄 아는지 물어보는 문제이다!

 

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;

        stk = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(stk.nextToken());
        int m = Integer.parseInt(stk.nextToken());

        int cnt = 1;
        HashMap<Integer, String> num_name_Map = new HashMap<>();
        HashMap<String, Integer> name_num_Map = new HashMap<>();

        for (int i = 0; i < n; i++) {
            String input = br.readLine();
            num_name_Map.put(cnt, input);
            name_num_Map.put(input, cnt);
            cnt++;
        }
        for (int i = 0; i < m; i++) {
            String input = br.readLine();
            char first = input.charAt(0);
            boolean isitnum = true;
            if('A'<=first && first<='Z'){
                isitnum = false;
            }
            if(isitnum){
                // num
                bw.write(num_name_Map.get(Integer.valueOf(input))+"\n");
            } else {
                // name
                bw.write(name_num_Map.get(input)+"\n");
            }
        }

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

java hash_map

JAVA 의 해쉬맵은 array 와 linked-list 로 이루어짐.

그래서 KEY 값을 안다면 O(1) 안에 ARRAY 에서 꺼내올 수 있는 것임.

만약 Collision 이 발생한다면 Linked-LIst Chaining 을 수행함.

 

get, put, remove, containsKey : O(1) ~ O(n)

containsValue : O(n)

 

Collision 이 많이 발생하여 Linked-List 가 너무 길어지면 성능을 개선하기 위해 JAVA 8 부터는 Tree 구조로 변경한다고 함.

 

 

D. 양팔 저울 BOJ 2629

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

2629번: 양팔저울

난이도	Gold 3
풀이 시간	풀이가 안떠올라서 구글링함..😢
분류	백트래킹, DP
시간복잡도
공간복잡도

태그를 열어보니 냅색 문제라고 되어 있어서, 이를 고려하면서 풀려고 했지만

 

그냥 백트래킹을 돌면서 dp 를 채우는 방식이 조금 더 직관적인 것 같다

 

dp[idx][w] ; idx 까지의 추를 확인하였을 때 w 라는 무게를 만들 수 있는지 여부

라고 정의하자.

 

그리고 idx 번째의 추를 확인하면서 우리가 할 수 있는 동작은 아래의 3 가지만 가능하다.

1. 구슬의 맞은편에 추를 올려놓는다.

▶이러한 경우에는 w+weight[idx] 무게를 확인할 수 있게 된다.

2. 구슬과 같은 편에 추를 올려놓는다.

▶이러한 경우에는 Math.abs( w-weight[idx] ) 무게를 확인할 수 있게 된다.

3. 해당 추를 올려놓지 않는다.

▶이러한 경우에는 w 무게를 확인할 수 있게 된다.

 

이를 재귀함수 형태로 구현하면 된다.

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

public class Main {
    static boolean [][] dp;
    static int n;
    static int [] weight;
    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;

        n = Integer.parseInt(br.readLine()); // 추의 개수
        weight = new int[n+1];
        stk = new StringTokenizer(br.readLine());
        int total = 0;
        for(int i = 0 ; i < n; i++){
            weight[i] = Integer.parseInt(stk.nextToken());
            total += weight[i];
        }

        dp = new boolean[n+1][15001];
        solve(0,0);

        int m = Integer.parseInt(br.readLine()); // 쿼리 개수
        stk = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < m; i ++){
            int target = Integer.parseInt(stk.nextToken());
            if(target > 500*30)
                bw.write("N ");
            else if(dp[n][target])
                bw.write("Y ");
            else bw.write("N ");

        }

        bw.flush();
        bw.close();
    }
    static void solve(int idx, int w){
        if(idx>n)
            return;
        if(dp[idx][w])
            return;
        dp[idx][w] = true;
        solve(idx+1, w + weight[idx]); // 구슬의 맞은 편에 추를 올리는 경우
        solve(idx+1, w); // 추를 올리지 않는 경우
        solve(idx+1, Math.abs(w-weight[idx])); // 구슬과 같은 편에 추를 올리는 경우
    }
}