📙[Algo] 24.04.02 알고리즘

알고리즘 문제) BOJ 1238. 파티

• 링크 : https://www.acmicpc.net/problem/1238

문제 요약

• N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 있음
• N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다
• 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비
• 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다
• N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라

시간 제한

• 1초

입력

• 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력
• 두 번째 줄부터 M+1번째 줄까지
  • i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti
  • 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개
• 모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다

출력

• N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력

접근법

4개의 마을 존재

8개의 도로 존재

파티 장소 → 2번 마을

1→2 : 4

1→3 : 2

1→4 : 7

2→1 : 1

2→3 : 5

3→1 : 2

3→4 : 4

4→2 : 3

1번 : 4+1

2번 : 0

3번 : (2+4) + (1+2)

4번 : 3+(1+2+4)

⇒ 각 마을 번호별로 start → x,x → start 의 최소값들을 구하고 합한 후, 그 중 최댓값 출력(다익스트라 알고리즘 메소드 구현)

코드

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

public class Main {
    static int N, M, X;
    static ArrayList<Node>[] list;
    static PriorityQueue<Node> pq = new PriorityQueue<>();
    static boolean[] visited;
    static int[] back;
    static int[] go;

    static class Node implements Comparable<Node>{
        int no;
        int weight;

        Node(int no, int weight) {
            this.no = no;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node node) {
            return this.weight - node.weight;
        }
    }

    static void daijk(int start, int[] dist) {
        pq.offer(new Node(start, 0));
        dist[start] = 0;

        int cur, nxt, nd;
        while (!pq.isEmpty()) {
            cur = pq.poll().no;

            if (visited[cur]) continue;

            visited[cur] = true;

            for (Node node : list[cur]) {
                nxt = node.no;
                nd = dist[cur] + node.weight;

                dist[nxt] = Math.min(dist[nxt], nd);

                pq.offer(new Node(nxt, dist[nxt]));
            }

        }
    }

    public static void main(String[] args) throws  IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());

        list = new ArrayList[N + 1];
        for (int i = 0; i < N + 1; i++) {
            list[i] = new ArrayList<>();
        }

        int from, to, weight;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            from = Integer.parseInt(st.nextToken());
            to = Integer.parseInt(st.nextToken());
            weight = Integer.parseInt(st.nextToken());

            list[from].add(new Node(to, weight));
        }

        visited = new boolean[N + 1];

        back = new int[N + 1];
        Arrays.fill(back, 1 << 30);
        daijk(X, back);

        go = new int[N + 1];
        int answer = 0;
        for (int i = 1; i <= N; i++) {
            Arrays.fill(go, 1 << 30);
            Arrays.fill(visited, false);
            daijk(i, go);

            answer = Math.max(answer, go[X] + back[i]);
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 2211. 네트워크 복구

• 링크 : https://www.acmicpc.net/problem/2211

문제 요약

• N(1 ≤ N ≤ 1,000)개의 컴퓨터로 구성된 네트워크
• 통신을 할 때에는 서로 직접 연결되어 있는 회선을 이용할 수도 있으며, 회선과 다른 컴퓨터를 거쳐서 통신을 할 수도 있다
• 회선을 이용해서 통신을 하는데 걸리는 시간이 서로 다를 수 있다
• 한 컴퓨터가 공격을 받게 되면, 네트워크를 통해 슈퍼컴퓨터에 이 사실이 전달이 되고, 그러면 슈퍼컴퓨터에서는 네트워크를 이용해서 보안 패킷을 전송하는 방식을 사용
• 아래 조건을 만족하면서 네트워크를 복구하는 방법을 알아내는 프로그램을 작성
  • 최소 개수의 회선만을 복구 → 네트워크를 복구한 후에 서로 다른 두 컴퓨터 간에 통신이 가능하도록 복구
  • 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다

시간 제한

• 2초

입력

• 첫째 줄에 두 정수 N, M
• M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C
  • A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결
• 1번 컴퓨터는 보안 시스템을 설치할 슈퍼컴퓨터
• 모든 통신은 완전쌍방향 방식으로 이루어지기 때문에, 한 회선으로 연결된 두 컴퓨터는 어느 방향으로도 통신할 수 있다

출력

• 첫째 줄에 복구할 회선의 개수 K를 출력
• 다음 K개의 줄에는 복구한 회선을 나타내는 두 정수 A, B를 출력
• 답이 여러 개 존재하는 경우에는 아무 것이나 하나만 출력

접근법

• 원래 회선
  1↔2 : 1
  1↔4 ; 4
  1↔3 : 1
  4↔2 : 2
  4↔3 : 3
• 회선 복구
  1↔2 : 1
  3↔1 : 1
  4↔2 : 2
  
  • 1번 조건
    • 원래 회선 이라면 슈퍼컴퓨터와 다른 컴퓨터들이 통신할 때 1+1+4 비용이 든다
    • 회선 복구 후에는 1+1+3으로 더 적은 비용이 든다. ⇒ 충족
  • 2번 조건
    • 모든 컴퓨터가 통신할 수 있도록 최소 회선만 복구 해야 한다.
    • ⇒ 즉, 회선을 복구했을 때 모든 컴퓨터끼리 통신이 가능한지 체크

고민

• 결국 최소한으로 복구하는 부분을 모르겠어서 풀이를 참고했다.
  • 개수는 N-1로 고정이다. 그것보다 작아지면 연결 못하는 회선이 존재할 테고, 최소 N-1개로 고정이 된다.
  • 또한 다익스트라를 돌면서 최소 경로를 갱신하는 부분에 해당 회선의 부모노드를 저장해두면 최소 비용 경로를 파악할 수 있다는 점을 활용 했다.
  ⇒ 이 부분이 아직 명확하지 않은 걸 보면 다익스트라 알고리즘을 제대로 이해한 느낌은 아니다.. 좀 더 공부해야지

코드

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

public class Main {
    static int N, M;
    static ArrayList<Node>[] lists;
    static boolean[] visited;
    static int[] dist;
    static int[] parent;

    static class Node implements Comparable<Node> {
        int no;
        int weight;

        Node(int no, int weight) {
            this.no = no;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node node) {
            return this.weight - node.weight;
        }
    }

    static void daijk(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        dist[start] = 0;

        int cur, nxt, nd;
        while (!pq.isEmpty()) {
            cur = pq.poll().no;

            if (visited[cur]) continue;

            visited[cur] = true;

            for (Node node : lists[cur]) {
                nxt = node.no;
                nd = dist[cur] + node.weight;

                if (dist[nxt] > nd) {
                    dist[nxt] = nd;
                    parent[nxt] = cur;
                }

                pq.offer(new Node(nxt, dist[nxt]));
            }
        }
    }

    public static void main(String[] args) throws  IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

        int A, B, C;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            A = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());

            lists[A].add(new Node(B, C));
            lists[B].add(new Node(A, C));
        }

        visited = new boolean[N + 1];
        parent = new int[N + 1];
        dist = new int[N + 1];
        Arrays.fill(dist, 1 << 30);

        daijk(1);

        sb.append((N - 1) + "\\n");
        for (int i = 2; i <= N; i++) {
            sb.append(i + " " + parent[i] + "\\n");
        }

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 4485. 녹색 옷 입은 애가 젤다지? 

• 링크 : https://www.acmicpc.net/problem/4485

문제 요약

• 링크는 이 동굴의 반대편 출구, 제일 오른쪽 아래 칸인 [N-1][N-1]까지 이동해야 한다
• 각 칸마다 도둑루피가 있는데, 이 칸을 지나면 해당 도둑루피의 크기만큼 소지금을 잃게 된다
• 잃는 금액을 최소로 하여 동굴 건너편까지 이동해야 하며, 한 번에 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다
• 링크가 잃을 수밖에 없는 최소 금액은 얼마

시간 제한

• 1초

입력

• 여러 개의 테스트 케이스로 이루어짐
• 각 테스트 케이스별로
  • 첫째 줄에는 동굴의 크기를 나타내는 정수 N이 주어진다. (2 ≤ N ≤ 125)
    • N = 0인 입력이 주어지면 전체 입력이 종료
  • N개의 줄에 걸쳐 동굴의 각 칸에 있는 도둑루피의 크기가 공백으로 구분되어 차례대로 주어진다.
    • 모든 정수는 0 이상 9 이하

출력

• 각 테스트 케이스마다 한 줄에 걸쳐 정답을 형식에 맞춰서 출력
  • ex) Problem 1: 20

접근법

• 최단 경로가 아니라 최소 비용이기 때문에 다익스트라 사용
• 2차원 다익스트라 연습용

코드

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

public class Main {
    static int N;
    static int[][] arr;
    static boolean[][] visited;
    static int[][] dist;
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};

    static class Node implements Comparable<Node> {
        int row;
        int col;
        int weight;

        Node(int row, int col, int weight) {
            this.row = row;
            this.col = col;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node node) {
            return this.weight - node.weight;
        }
    }

    static void daijk(int row, int col) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(row, col, arr[row][col]));
        dist[row][col] = arr[row][col];

        int cr, cc, mr, mc;
        while (!pq.isEmpty()) {
            cr = pq.peek().row;
            cc = pq.poll().col;

            if (visited[cr][cc]) continue;

            visited[cr][cc] = true;

            for (int dir = 0; dir < 4; dir++) {
                mr = cr + delR[dir];
                mc = cc + delC[dir];

                if (mr < 0 || mc < 0 || N <= mr || N <= mc || visited[mr][mc]) continue;

                dist[mr][mc] = Math.min(dist[mr][mc], dist[cr][cc] + arr[mr][mc]);
                pq.offer(new Node(mr, mc, dist[mr][mc]));
            }
        }
    }

    public static void main(String[] args) throws  IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        StringBuilder sb = new StringBuilder();
        int nth = 1;
        while ((N = Integer.parseInt(br.readLine())) != 0) {
            sb.append("Problem " + (nth++) + ": ");

            arr = new int[N][N];

            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            visited = new boolean[N][N];
            dist = new int[N][N];

            for (int[] d : dist) {
                Arrays.fill(d, 1 << 30);
            }

            daijk(0, 0);

            sb.append(dist[N - 1][N - 1] + "\\n");
        }

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 2206. 벽 부수고 이동하기

• 링크 : https://www.acmicpc.net/problem/2206

문제 요약

• N×M의 행렬로 표현되는 맵
• 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽
• (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동
  • 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다
• 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동
• 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸
• 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성

시간 제한

• 2초

입력

• 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)
• 다음 N개의 줄에 M개의 숫자로 맵이 주어진다
  • (1, 1)과 (N, M)은 항상 0이라고 가정

출력

• 첫째 줄에 최단 거리를 출력
  • 불가능할 때는 -1을 출력

접근법

• 이미 한 번 벽을 부순 경우, 부수지 않은 경우 두 차원을 고려해서 bfs

코드

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

public class Main {
    static int N, M;
    static int[][] arr;
    static boolean[][][] visited;
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};

    static int bfs(int row, int col, int wall) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{row, col, wall});
        visited[wall][row][col] = true;

        int cr, cc, cw, mr, mc, size, dist = 1;
        while (!q.isEmpty()) {
            size = q.size();

            for (int s = 0; s < size; s++) {
                cr = q.peek()[0];
                cc = q.peek()[1];
                cw = q.poll()[2];

                if (cr == N - 1 && cc == M - 1) return dist;

                for (int dir = 0; dir < 4; dir++) {
                    mr = cr + delR[dir];
                    mc = cc + delC[dir];

                    if (mr < 0 || mc < 0 || N <= mr || M <= mc) continue;

                    // 이미 벽을 만난 경우 또 벽을 만났을 경우 pass
                    if (arr[mr][mc] == 1 && cw == 1) continue;

                    // 방문체크
                    if (visited[cw + arr[mr][mc]][mr][mc]) continue;

                    q.offer(new int[]{mr, mc, cw + arr[mr][mc]});
                    visited[cw + arr[mr][mc]][mr][mc] = true;
                }
            }

            dist++;
        }

        return -1;
    }

    public static void main(String[] args) throws  IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N][M];
        String input;
        for (int i = 0; i < N; i++) {
            input = br.readLine();
            for (int j = 0; j < M; j++) {
                arr[i][j] = input.charAt(j) - '0';
            }
        }

        visited = new boolean[2][N][M];
        bw.write(String.valueOf(bfs(0, 0, 0)));
        bw.flush();
        bw.close();
        br.close();
    }
}