[Baekjoon] 14620번 : 꽃길

1. 문제

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

• 방향 벡터 문제

// 문제
2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신
하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다.

진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로
진아는 다음해 식목일 부터 꽃길을 걸을 수 있다.

하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로
세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다.

꽃밭은 N*N의 격자 모양이고
진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수 있다.
꽃의 씨앗은 그림 (a)처럼 심어지며 1년 후 꽃이 피면 그림 (b)모양이 된다.

꽃을 심을 때는 주의할 점이있다.
어떤 씨앗이 꽃이 핀 뒤 다른 꽃잎(혹은 꽃술)과 닿게 될 경우 두 꽃 모두 죽어버린다.
또 화단 밖으로 꽃잎이 나가게 된다면 그 꽃은 죽어버리고 만다.

그림(c)는 세 꽃이 정상적으로 핀 모양이고 그림(d)는 두 꽃이 죽어버린 모양이다.

하이테크 앞 화단의 대여 가격은 격자의 한 점마다 다르기 때문에
진아는 서로 다른 세 씨앗을 모두 꽃이 피게하면서
가장 싼 가격에 화단을 대여하고 싶다.

단 화단을 대여할 때는 꽃잎이 핀 모양을 기준으로 대여를 해야하므로
꽃 하나당 5평의 땅을 대여해야만 한다.

돈이 많지 않은 진아를 위하여 진아가 꽃을 심기 위해 필요한 최소비용을 구해주자!

// 입력
입력의 첫째 줄에 화단의 한 변의 길이 N(6≤N≤10)이 들어온다.
이후 N개의 줄에 N개씩 화단의 지점당 가격(0≤G≤200)이 주어진다.

// 출력
꽃을 심기 위한 최소 비용을 출력한다.

// 예제 입력 1
6
1 0 2 3 3 4
1 1 1 1 1 1
0 0 1 1 1 1
3 9 9 0 1 99
9 11 3 1 0 3
12 3 0 0 0 1

// 예제 출력 1
12

2. 핵심 아이디어

• 전수조사와 방향벡터를 이용

3. Python 문제풀이

import sys
input = sys.stdin.readline

n = int(input())
g = [list(map(int, input().split())) for i in range(n)]

ans = 10000
dx, dy = [0, 0, 0, 1, -1], [0, 1, -1, 0, 0]

def ck(arr) :
  ret = 0
  flow = []
  for flower in arr :
    x = flower // n
    y = flower % n
    if x == 0 or x == n - 1 or y == 0 or y == n - 1 :
      return 10000
    for w in range(5) :
      flow.append((x + dx[w], y + dy[w]))
      ret += g[x + dx[w]][y + dy[w]]

  if len(set(flow)) != 15 :
    return 10000

  return ret

for i in range(n * n) :
  for j in range(i + 1, n * n) :
    for k in range(j + 1, n * n) :
      ans = min(ans, ck([i, j, k]))

print(ans)

4. Java 문제풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
	static int[][]matrix;
	static int n;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		matrix = new int[n][n];
		int answer = Integer.MAX_VALUE;

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

		for (int i=0; i<(n*n); i++) {
			for (int j=0; j<(n*n); j++) {
				for (int k=0; k<(n*n); k++) {
					ArrayList<Integer> list = new ArrayList<>();
					list.add(i);
					list.add(j);
					list.add(k);
					answer = Math.min(answer, findCost(list));
				}
			}
		}
		System.out.println(answer);
	}

	static int findCost(ArrayList<Integer> list) {
		int[] dx = {0, -1, 1, 0, 0};
		int[] dy = {0, 0, 0, -1, 1};
		boolean[][] check = new boolean[n][n];

		int result = 0;
		for (int i: list) {
			int x = i / n;
			int y = i % n;

			if (x == 0 || x == (n - 1) || y == 0 || y == (n - 1)) {
				return 10000;
			}

			for (int j=0; j<5; j++) {
				if (!check[x+dx[j]][y+dy[j]]) {
					check[x+dx[j]][y+dy[j]] = true;
					result += matrix[x+dx[j]][y+dy[j]];
				}
				else return 10000;
			}
		}
		return result;
	}
}