[백준_14620번] 꽃길

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

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)이 주어진다.

 

[코드]

import java.util.Scanner;

public class BaekJoon_14620 {
	static int[][] map;
	static boolean[][] visited;
	static int n,min=Integer.MAX_VALUE;
	static int[] dx= {-1,1,0,0};
	static int[] dy= {0,0,-1,1};
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		map=new int[n][n];
		visited=new boolean[n][n];
		
		// 각 화단의 비용 입력 받기
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				map[i][j]=sc.nextInt();
		
		dfs(0,0);
		System.out.println(min);
	}
	
	static void dfs(int depth, int sum) {
		// 3개의 꽃을 심었다면 최소 비용 갱신
		if(depth==3) {
			min=Math.min(min, sum);
			return;
		}
		
		// 모든 화단 탐색
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				// i행 j열에 꽃을 심을 수 있다면
				if(isPossible(i,j)) {
					int temp=expense(i,j); // 비용 계산
					
					// 꽃을 심은 자리와 상,하,좌,우 방문처리
					visited[i][j]=true;
					for(int k=0;k<4;k++) {
						int nx=i+dx[k];
						int ny=j+dy[k];
						
						visited[nx][ny]=true;
					}
					
					dfs(depth+1,sum+temp); // 개수를 1 늘리고, 비용을 더한 후 재귀호출
					
					// 다음 경우의 수를 위해 값 초기화
					visited[i][j]=false;
					for(int k=0;k<4;k++) {
						int nx=i+dx[k];
						int ny=j+dy[k];
						
						visited[nx][ny]=false;
					}
				}
			}
		}
	}
	
	// x행 y열에 꽃을 심을 수 있는지 판별하는 함수
	static boolean isPossible(int x, int y) {
		// 해당 자리가 이미 방문처리 되어있다면 false return
		if(visited[x][y]==true)
			return false;
		
		// 꽃이 피어나 꽃잎이 생길 수 있는지 확인
		for(int i=0;i<4;i++) {
			int nx=x+dx[i];
			int ny=y+dy[i];
			
			// 꽃잎이 배열의 범위를 벗어난다면 해당 자리에 꽃을 심을수 없음
			if(nx>=n||ny>=n||nx<0||ny<0)
				return false;
			
			// 꽃잎의 자리에 다른 꽃이 핀 경우도 꽃을 심을 수 없음
			if(visited[nx][ny])
				return false;
		}
		// 위의 경우가 아니라면 꽃을 심을 수 있음
		return true;
	}
	
	// x행 y열에 꽃을 심었다면 비용 계산
	static int expense(int x, int y) {
		int sum=map[x][y]; // 씨앗 자리 비용
		
		// 꽃잎 자리 비용 계산
		for(int k=0;k<4;k++) {
			int nx=x+dx[k];
			int ny=y+dy[k];
			
			sum+=map[nx][ny];
		}
		return sum;
	}
}

 

[고찰]

 이번 문제는 난이도는 높지는 않았지만 고려할 조건이 많아 까다롭게 느껴지는 문제였다. 코드를 짜다보니 구성이 복잡해지고 헷갈려 다른 사람의 코드를 참고하며 코드의 로직을 다듬었다. 

 이번 문제는 각 배열의 자리마다 꽃을 심을 수 있는지 모두 탐색하는 방법으로 해결할 수 있다. 꽃을 심을 수 있는 경우는 씨앗을 심는 자리와, 꽃잎이 피어나는 상, 하, 좌, 우에 다른 꽃이 심어져 있지 않은 경우이다. boolean 배열을 사용하여 꽃의 자리는 true 값으로 변경하는 방식으로 꽃의 유뮤를 판단했다. 이후 꽃을 심을 수 있다면 비용을 계산하고, 꽃을 3개 모두 심었다면 최소 비용을 갱신해는 과정까지 모두 구현하면 정답 처리를 받을 수 있다. 이처럼 완전탐색 문제는 백트래킹과 접목하여 해결하는 문제가 많고 유형도 다양해 익숙해질 필요가 있다고 느꼈다.