14620번: 꽃길

문제

N x N 크기의 화단에 씨앗 3개를 심어서 꽃을 피우려고 합니다. 꽃이 피면 씨앗이 있는 칸을 포함해 상하좌우로 총 5칸의 공간을 차지하게 됩니다. 꽃끼리 잎이 닿거나 화단 밖으로 나가면 꽃이 죽어버립니다. 화단의 각 칸마다 대여 가격이 주어질 때, 3송이의 꽃을 모두 무사히 피우기 위한 최소 비용을 구하는 문제입니다.

• 입력: 첫째 줄에 화단의 한 변의 길이 N (6 ≤ N ≤ 10)이 주어집니다. 다음 N개의 줄에 걸쳐 화단의 지점당 가격이 주어집니다.
• 출력: 꽃을 심기 위한 최소 비용을 출력합니다.

링크: https://www.acmicpc.net/problem/14620

풀이: 3개의 좌표를 뽑는 완전탐색

화단의 최대 크기가 10 x 10 = 100칸으로 매우 작습니다. 따라서 100칸 중 3칸을 고르는 조합(Combination)을 모두 탐색하여도 시간 초과가 발생하지 않는 전형적인 브루트포스 문제입니다.

1. 좌표 리스트 생성: 입력을 받을 때 화단의 모든 (y, x) 좌표를 Node 객체로 만들어 list에 저장해 둡니다. 이를 통해 좌표를 쉽게 순회하고 조합을 구성할 수 있습니다.
2. 3개의 씨앗 위치 고르기: 3중 반복문을 사용하여 list에서 서로 다른 3개의 좌표 인덱스(p, q, r)를 고릅니다.
3. 비용 계산 및 유효성 검사 (getCost): 선택된 3개의 좌표를 중심으로 꽃이 필 수 있는지 검사합니다.
   • visited 배열을 선언하여 꽃잎이 차지하는 자리를 방문 처리합니다.
   • 중심 좌표와 상하좌우 4칸(dy, dx)을 확인합니다.
   • 만약 화단 범위를 벗어나거나(ny < 0 || nx < 0 || ny >= n || nx >= n), 다른 꽃잎과 이미 겹친다면(visited[ny][nx] == true), 무효한 경우이므로 Integer.MAX_VALUE를 반환하여 최솟값 갱신을 막습니다.
   • 무사히 꽃을 피울 수 있다면 5칸의 가격을 모두 sum에 더해주고 누적된 비용을 반환합니다.
4. 최솟값 갱신: 반환된 비용을 바탕으로 전체 최솟값(ans)을 갱신하고, 모든 조합의 탐색이 끝난 후 출력합니다.

코드

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

public class Main {
    // 최소 비용을 구해야 하므로 정수 최댓값으로 초기화
    static int n, ans = Integer.MAX_VALUE;
    static int[][] a;
    static List<Node> list = new ArrayList<>();
    
    // 상하좌우 델타 배열
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -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));

       n = Integer.parseInt(br.readLine());
       a = new int[n][n];

       // 화단 가격 입력 및 모든 좌표를 리스트에 저장
       for (int i = 0; i < n; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          for (int j = 0; j < n; j++) {
             a[i][j] = Integer.parseInt(st.nextToken());
             list.add(new Node(i, j));
          }
       }

       // 리스트에 담긴 좌표 중 3개를 뽑는 조합 (3중 for문)
       for (int i = 0; i < list.size() - 2; i++) {
          for (int j = i + 1; j < list.size() - 1; j++) {
             for (int k = j + 1; k < list.size(); k++) {
                // 선택된 3개의 씨앗 위치로 최소 비용 갱신 시도
                ans = Math.min(ans, getCost(i, j, k));
             }
          }
       }

       bw.write(ans + "");
       bw.flush();
       bw.close();
       br.close();
    }

    // 3개의 좌표(인덱스 p, q, r)에 꽃을 피울 때의 비용 계산
    static int getCost(int p, int q, int r) {
       Node[] nodes = new Node[3];
       nodes[0] = list.get(p);
       nodes[1] = list.get(q);
       nodes[2] = list.get(r);

       int sum = 0;
       boolean[][] visited = new boolean[n][n]; // 꽃잎 겹침 방지용 방문 배열
       
       for (int i = 0; i < 3; i++) {
          int y = nodes[i].y;
          int x = nodes[i].x;
          
          // 씨앗 중심부 처리
          sum += a[y][x];
          visited[y][x] = true;
          
          // 상하좌우 꽃잎 처리
          for (int j = 0; j < 4; j++) {
             int ny = y + dy[j];
             int nx = x + dx[j];
             
             // 화단을 벗어나거나 다른 꽃잎과 겹치면 실패 처리 (최댓값 반환)
             if (ny < 0 || nx < 0 || ny >= n || nx >= n || visited[ny][nx]) {
                return Integer.MAX_VALUE;
             }
             
             sum += a[ny][nx];
             visited[ny][nx] = true;
          }
       }
       return sum; // 3송이 모두 성공적으로 피웠다면 총 비용 반환
    }

    // 좌표를 담기 위한 이너 클래스
    static class Node {
       int y, x;

       Node(int y, int x) {
          this.y = y;
          this.x = x;
       }
    }
}

알고리즘 분류

브루트포스 알고리즘 (완전탐색), 조합 (Combination)