[백준 14620번 / C++] 꽃길

완전 탐색 문제이다. 

 

1. dfs 구현은 동일 

2. 현재 지점에서 상하좌우를 돌아봤을 때 맵을 초과했거나 또는 이미 만개한 꽃잎과 겹치는 부분이 있을 경우 continue

3. 위의 조건을 통과하였다면 현재위치 포함 상하좌우 모두 visited 라는 배열에 저장 후 dfs 호출 

4. dfs 호출 이후 코드는 visited 배열을 다시 0으로 초기화. (다른 지역에서 꽃이 필 경우도 모두 탐색해야하기 때문) 

#include <iostream>
#include <algorithm>
#include <climits>
int dx[4] = { 0,0,-1,1 }; 
int dy[4] = { -1,1,0,0 }; 
int n; 
int map[10][10]; 
int visited[10][10]; 
int result = INT_MAX; 
using namespace std; 
void dfs(int sum, int cnt) {
	if (cnt == 3) {
		result = min(result, sum); return; 
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int check = 0; 
			int nx, ny; 		
			for (int k = 0; k < 4; k++) {
				nx = j + dx[k]; 
				ny = i + dy[k]; 
				if (nx < 0 || nx >= n || ny < 0 || ny >= n)continue; 
				if (visited[ny][nx])continue; 
				check++; 
			}
			if (check == 4) {
				int ssum = map[i][j]; 
				for (int k = 0; k < 4; k++) {
					nx = j + dx[k];
					ny = i + dy[k];
					visited[ny][nx] = 1; 		
					ssum += map[ny][nx]; 
				}
				visited[i][j] = 1;
				sum += ssum; 
				cnt++; 
				dfs(sum, cnt); 
				sum -= ssum; 
				cnt--; 
				for (int k = 0; k < 4; k++) {
					nx = j + dx[k];
					ny = i + dy[k];
					visited[ny][nx] = 0;				
				}
				visited[i][j] = 0;
			
			}
		}
	}

}
int main() {
	cin >> n; 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j]; 
		}
	}
	dfs(0, 0);
	cout << result; 
}

 

14620번: 꽃길