📙[Algo] 24.09.09 알고리즘

알고리즘 문제) PG [PCCP 기출문제] 2번 / 석유 시추

• 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/250136

프로그래머스

문제 요약

• 세로길이 N, 가로길이 M인 격자 모양 땅 속에 석유 발견
• 석유는 여러 덩어리로 나뉘어 묻힘
• 가장 많은 석유를 뽑을 수 있는 시추관 위치를 찾으려 한다
• 시추관은 특정 열을 관통하는 형태이다.
• 이때, 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 RETURN

입력

• 2차원 배열 형태로 땅 정보가 주어짐 (0 : 빈 땅, 1 : 석유) : 1 <= N, M <= 500

출력

• 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 RETURN

접근법

• dfs + union & find로 접근해서 풀었다.
• 먼저 각 격자칸에 0 ~ n*m-1 번호를 붙일 수 있다.
  • 즉, 2차원 배열의 격자칸을 각각 하나의 노드로 볼 수 있다.
• dfs로 석유가 묻어있는 곳(1)만 계속 탐색하면서, 석유가 묻힌 노드들을 union 함수를 통해 하나의 연결요소로 묶는다.
  • 이때, 우리는 석유 덩어리 크기를 알아야 하므로, 노드가 속한 연결요소 크기를 담는 배열(size)를 갱신해준다 ⇒ 연결요소 크기가 작은 것을 큰 것으로 옮기면서, 해당 노드를 부모로 갱신한다. ⇒ 그럼 최종적으로 연결요소의 부모노드의 크기가 곧 석유 덩어리 크기(연결요소 크기)가 된다.
• 이제, 열을 기준으로 0 → m-1까지 석유 시추를 진행한다.
  • 만약 1을 만났다면, 해당 칸이 속한 연결요소의 부모 노드 번호를 찾아서(find함수) set자료구조에 담아두었다. ⇒ 같은 연결요소를 또 만날 수 있기 때문에 중복 제거를 위해 사용
  • 하나의 열에 속한 행들을 모두 살펴 봤다면, set을 순회하면서 각각의 size들을 합계변수 sum에 누적해서 합해준다.
  • 마지막으로 sum변수를 answer와 비교하여 최대값으로 갱신한다.
  • 위 과정을 열 번호 0 ~ m-1까지 반복한다.

코드

import java.util.*;
import java.io.*;
/*
    [문제 요약]
    세로길이 N, 가로길이 M인 격자 모양 땅 속에 석유 발견
    석유는 여러 덩어리로 나뉘어 묻힘
    가장 많은 석유를 뽑을 수 있는 시추관 위치를 찾으려 한다
    시추관은 특정 열을 관통하는 형태이다.
    이때, 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 RETURN
    
    [입력]
    2차원 배열 형태로 땅 정보가 주어짐 (0 : 빈 땅, 1 : 석유) : 1 <= N, M <= 500

*/

class Solution {
    static int n, m;
    static int[] parent;
    static int[] size;
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};
    static boolean[][] visited;
    
    static int find (int x) {
        if (parent[x] == x) return parent[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;
        
        if (size[a] >= size[b]) {
            parent[b] = a;
            size[a] += size[b];
        } else {
            parent[a] = parent[b];
            size[b] += size[a];
        }
    }
    
    static void dfs(int row, int col, int[][] land) {
        visited[row][col] = true;
        int mrow, mcol, toNum;
        for (int dir = 0; dir < 4; dir++) {
            mrow  = row + delR[dir];
            mcol = col + delC[dir];
            
            if (mrow < 0 || mcol < 0 || n <= mrow || m <= mcol 
                    || land[mrow][mcol] == 0 || visited[mrow][mcol]) continue;

            union(row * m + col, mrow * m + mcol);
            dfs(mrow, mcol, land);
        }
    }
    
    public int solution(int[][] land) {
        int answer = 0;
        
        n = land.length; // 세로 길이
        m = land[0].length;  // 가로 길이
        parent = new int[n * m + 1];
        for (int i = 0; i < n * m + 1; i++) {
            parent[i] = i;
        }
        size = new int[n * m + 1];
        Arrays.fill(size, 1);
        visited = new boolean[n][m];
        
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < m; col++) {
                if (visited[row][col] || land[row][col] == 0) continue;
                
                dfs(row, col, land);
            }
        }
        
        Set<Integer> set = new TreeSet<>();
        int sum = 0;
        for (int col = 0; col < m; col++) {
            for (int row = n - 1; row >= 0; row--) {
                if (land[row][col] == 1) {
                    set.add(find(row * m + col));
                }
            }
            
            for (Integer el : set) {
                sum += size[el];
            }
            
            answer = Math.max(answer, sum);
                
            sum = 0;
            set.clear();
        }
        
        return answer;
    }
}

 

알고리즘 문제) BOJ 23097.Rescue Mission

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

문제 요약

• 죄수를 구출하고 운송할 10대의 트럭이 존재한다
• 이때, 각 N개의 기차칸마다 죄수들이 존재할 때, 특정 위치에서 시작하면 다음 칸들은 연속적으로 공격하며 죄수를 구출해야한다.
  • 이때, 각 트럭에 태우는 죄수의 수가 동일해야한다.
    • 만약 이 조건을 만족할 수 없다면, 공격을 할 수 없다.
• 각 칸에서 공격을 시작했을 때, 몇 개의 칸을 공격해야 임무를 완수할 수 있는지 구하시오

시간 제한

• 2초

입력

• 기차 칸의 수 N(1 ≤ N ≤ 10^5)을 나타내는 정수 N
• 두 번째 줄에는 0부터 9까지의 N개의 값이 주어지며, 각 칸에 수송된 죄수의 수를 의미

출력

• i번째 칸에서 공격을 시작할 때, 공격해야하는 기차 칸의 수는?
  • 해당 기차 칸에서 시작한 임무가 완료될 수 없다면, 해당 값은 -1

접근법

• 누적합 배열을 만들어서, 각 기차칸에서 공격했을 때, 특정 인덱스까지 구간합이 10으로 나누어떨어지는 경우 지나간 칸의 개수(현재칸 인덱스 - 시작칸 인덱스 + 1)를 기록했다.

코드

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

public class Main {

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

        int N = Integer.parseInt(br.readLine());
        int[] prefix = new int[N + 1];
        int num;
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            num = Integer.parseInt(st.nextToken());
            prefix[i] = prefix[i - 1] + num;
        }

        int sum;
        StringBuilder sb = new StringBuilder();
        int[] ans = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = i; j <= N; j++) {
                sum = prefix[j] - prefix[i - 1];

                if (sum % 10 == 0) {
                    ans[i] = j - i + 1;
                    break;
                }
            }
        }
        for (int i = 1; i <= N; i++) {
            if (ans[i] > 0) sb.append(ans[i]).append(" ");
            else sb.append(-1).append(" ");
        }
        System.out.println(sb);
    }
}