📙[Algo] 24.04.16 알고리즘

알고리즘 문제) BOJ 7569. 토마토

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

문제 요약

• M*N크기의 격자가 H개만큼 쌓여 있음
• 익은 토마토의 상, 하, 좌, 우, 앞, 뒤에있는 방향의 토마토는 영향을 받음
• 이때 모든 토마토들이 며칠이 지나야 다 익는지 최소 일수 구하기

시간 제한

• 1초

입력

• 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H
  • M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수
  • 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100
• 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다
  • 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸
  • 이러한 N개의 줄이 H번 반복하여 주어진

출력

• 토마토가 모두 익을 때까지 최소 며칠이 걸리는지 출력
  • 장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력

코드

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

public class Main {
    static int M, N, H;
    static int[][][] box;
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};
    static int[] delH = {-1, 1};
    static boolean[][][] visited;
    static Queue<Node> q = new LinkedList<>();
    static int tomatoCnt;
    static int answer;

    static class Node {
        int height;
        int row;
        int col;

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

    static void bfs() {
        int size, ch, cr, cc, mh, mr, mc;
        while (!q.isEmpty()) {
            size = q.size();

            if (tomatoCnt == 0) return;

            for (int i = 0; i < size; i++) {
                ch = q.peek().height;
                cr = q.peek().row;
                cc = q.poll().col;

                // 상하좌우
                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;

                    if (visited[ch][mr][mc] || box[ch][mr][mc] != 0) continue;

                    q.offer(new Node(ch, mr, mc));
                    visited[ch][mr][mc] = true;
                    box[ch][mr][mc] = 1;
                    tomatoCnt--;
                }

                // 앞뒤
                for (int dir = 0; dir < 2; dir++) {
                    mh = ch + delH[dir];

                    if (mh < 0 || H <= mh) continue;

                    if (visited[mh][cr][cc] || box[mh][cr][cc] != 0) continue;

                    q.offer(new Node(mh, cr, cc));
                    visited[mh][cr][cc] = true;
                    box[mh][cr][cc] = 1;
                    tomatoCnt--;
                }
            }
            answer++;
        }
    }

    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());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());

        box = new int[H][N][M];
        visited = new boolean[H][N][M];

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

                    if (box[i][j][k] == 1){
                        q.offer(new Node(i, j, k));
                        visited[i][j][k] = true;
                    } else if (box[i][j][k] == 0) {
                        // 안익은 토마토 개수 세기
                        tomatoCnt++;
                    }
                }
            }
        }

        if (tomatoCnt == 0) {
            bw.write("0");
        } else {
            bfs();
            if (tomatoCnt > 0) bw.write("-1");
            else bw.write(String.valueOf(answer));
        }

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

 

알고리즘 문제) BOJ 1647. 도시 분할 계획

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

문제 요약

• 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다
  • 양방향(무방향) 간선
• 임의의 두 집 사이에 경로가 항상 존재
• 아래 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다
  • 두 개의 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할
  • 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다
  • 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다

시간 제한

• 2초

입력

• 집의 개수 N, 길의 개수 M
  • N은 2이상 10만이하인 정수
  • M은 1이상 100만이하인 정수
• M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어짐
  • A번 집과 B번 집을 연결하는 길의 유지비가 C (1 ≤ C ≤ 1,000)

출력

• 없애고 남은 길 유지비의 합의 최솟값을 출력

접근법

• MST구하고, 거기서 가장 간선이 큰 애를 하나 제거

코드

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

public class Main {
    static int N, M;
    static int[][] graph;
    static int[] parent;

    static int find(int x) {
        if (parent[x] == x) return x;

        parent[x] = find(parent[x]);
        return parent[x];
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b) return;

        parent[b] = a;
    }

    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());

        graph = new int[M][3];

        int v1, v2, c;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            v1 = Integer.parseInt(st.nextToken());
            v2 = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            graph[i][0] = v1;
            graph[i][1] = v2;
            graph[i][2] = c;
        }

        Arrays.sort(graph, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });

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

        int answer = 0;
        int max = 0;
        for (int i = 0; i < M; i++) {
            v1 = graph[i][0];
            v2 = graph[i][1];
            c = graph[i][2];

            if (find(v1) == find(v2)) continue;

            union(v1, v2);
            answer += c;
            max = Math.max(max, c);
        }

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