BOJ_14620_꽃길

1

구분: 브루트포스 알고리즘

언어: Java 
전략:

• 꽃밭의 정보를 담는 class 생성, 이를 ArrayList에 보관(조합에 유리)
• 꽃밭에서 3 자리를 조합으로 선정
• 각 자리에 꽃잎을 두었을 때, 겹치거나 범위가 나가는지 확인
• 꽃이 놓인 자리의 땅 값을 계산
• 최소 비용을 갱신하며 구해

---

2. 코드

import java.util.ArrayList;
import java.util.Scanner;
public class Main {
	static int[][] map;//전체 가격을 담을 배열
	static int n, min;
	//좌표, 가격을 담을 class
	static class Place{
		int x, y, cost;
		Place(int y, int x, int cost){
			this.y = y;
			this.x = x;
			this.cost = cost;
		}
	}
	//Place class를 담을 리스트 
	static ArrayList<Place> spot;
	static Place[] choice;//조합으로 선택된 것들을 담을 배열
	static int[] dx = {0,0,-1,1};
	static int[] dy = {-1,1,0,0};
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		spot = new ArrayList<>();
		choice = new Place[3];
		min = Integer.MAX_VALUE;
		map = new int[n][n];
		for(int i = 0; i<n; i++) {
			for(int j = 0; j<n; j++) {
				int a = scanner.nextInt();
				spot.add(new Place(i, j, a));
				map[i][j] = a;
			}
		}
		comb(0,0);
		System.out.println(min);
		
	}//main
	
	private static void comb(int cnt, int start) {
		
		if(cnt == 3) {
			
			//꽃잎이 겹치는지 확인
			if(!isOkay())
				return;
			//가격 확인
			int cost = getTotal();
			min = Math.min(cost, min);
			return;
		}
		
		//3개 자리 선정 - 조합
		for(int i = start; i<n*n; i++) {
			Place p = spot.get(i);
			//맨 끝은 그냥 뺴자
			if(p.y == 0 || p.x == 0)
				continue;
			choice[cnt] = p;
			comb(cnt+1, i+1);
		}
	}//comb
	
	//선택된 땅의 가격을 리턴하는 함수 
	private static int getTotal() {
		int money = 0;
		for(int i = 0; i<3; i++) {
			money+=choice[i].cost;
			for(int d = 0; d<4; d++) {
				int nx = choice[i].x + dx[d];
				int ny = choice[i].y + dy[d];
				money+=map[ny][nx];
			}
		}
		return money;
	}
	
	
	
	//겹치거나 범위를 벗어나는지 판단
	private static boolean isOkay() {
		boolean flag = true;
		boolean[][] visit = new boolean[n][n];
		
		loop:for(int i = 0; i<3; i++) {
			Place p = choice[i];
			//이미 방문했거나 범위 벗어나면 그만
			if(p.y<0 || p.x <0 || p.x>=n || p.y>=n || visit[p.y][p.x]) {
				flag = false;
				break loop;
			}
			//방문 처리
			visit[p.y][p.x] = true;
			//꽃 잎들 방문 여부, 범위 및 방문 처리
			for(int d = 0; d<4; d++) {
				int ny = p.y + dy[d];
				int nx = p.x + dx[d];
				if(ny<0 || nx<0 || ny>=n || nx>=n || visit[ny][nx]) {
					flag = false;
					break loop;
				}
				visit[ny][nx] = true;
			}
		}
		return flag;
	}
}

---

3

• 꽃들끼리 겹쳐지는 부분에 방문 처리나, 꽃술과 잎과의 겹침 부분을 빼먹어서 시간이 걸렸다
• 조합 - 조건 이런 유형을 연습하기 좋았다