[Silver 2] 14620 꽃길

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

14620번: 꽃길

 

이 문제는 DFS를 통한 완전 탐색을 이용해 해결해야한다.

 

꽃은 십자가 모양으로 키워지며, 3개의 꽃은 서로 겹치면 안된다.

이는 DFS를 통해 탐색을 진행하고 꽃을 키울 수 있는지 확인한 후 키울 수 있다면  밭의 비용을 십자가 모양으로 산출하면 된다.

 

꽃은 테투리 범위에 키울 수 없으므로 테투리까지 탐색하지 않아도 된다.

따라서 반복을 1부터 N-1까지 진행하는 것이며, DFS를 위한 탐색 범위도 N-1까지 하는 것이다.

 

코드를 설명하면 다음과 같다.

1. 밭의 비용을 입력 받는다.
2. 테투리를 제외하고 밭을 순회한다.
   1. 탐색한 밭의 좌표를 통해 꽃을 심을 수 있는지 확인한다.
      • 십자가 범위로 해당 좌표를 검사하고 이미 탐색한 장소이면 -1을 반환한다.
      • 뻗어 갈 수 있다면 해당 좌표의 비용을 저장한다.
        • 십자가 범위로 탐색을 진행하고 지나간 장소를 표시한다.
        • 지나간 장소의 비용을 누적한다.
      • 산출한 비용을 반환한다.
   2. DFS를 진행한다.
      • DFS를 3회 진행했다면 더 이상 진행하지 않고 탐색을 통해 구한 비용이 최소인 경우 저장한다.
      • DFS를 시작한 좌표 부터 테두리 전까지 반복을 진행한다.
        • 이미 방문한 좌표이면 무시한다.
        • 방문할 장소가 꽃을 심을 수 있는 장소인지 확인한다. (1번 과정 진행)
        • 꽃을 심을 수 있는 장소인 경우 (1번 과정의 반환 값이 -1이 아닌 경우) 현재 좌표와 산출한 비용을 누적하여 DFS를 진행
        • DFS를 3회 진행한 후 다른 경우를 찾기 위해 현재 방문 표시한 장소를 초기화
   3. 다른 경우를 찾기 위해 현재 방문 표시한 장소를 초기화

지금까지 완전 탐색(브루트 포스) 문제를 풀면서 깨달은 점이 생겼다.

바로 완전 탐색은 주로 함수 호출 스택을 통해 해결한다는 점이다.

지금까지 해결한 완전 탐색 문제는 A가 있다면 A를 수정하여 A1, A2, ... AN을 생성한다.

이어서 A1, A2, ..., AN을 수정하는 과정이 필요했다.

이를 위해서는 AN까지의 값 누적하고 특정 조건에 도달하면 값을 저장하는 일이 필요했다.

이는 함수를 특정 조건에 도달할 때 까지(주로 counter 사용) 호출하고 값을 담고(cost) 있다가

조건에 맞게 특정 변수(result)에 담으면 된다.

 

 

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

int N;
int result = 987654321;
int board[11][11];
int dy[] = { 0, 1, 0, -1 };
int dx[] = { 1, 0, -1, 0 };
bool visited[11][11];

void resetBoard(int y, int x) {
	visited[y][x] = false;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		visited[ny][nx] = false;
	}
}

int checkFlower(int y, int x) {
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (visited[ny][nx]) return -1;
	}
	int sum = board[y][x];
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		visited[ny][nx] = true;
		sum += board[ny][nx];
	}
	return sum;
}

void dfs(int y, int x, int counter, int cost) {
	if (counter == 3) {
		result = min(result, cost);
		return;
	}
	for (int i = y; i < N - 1; i++) {
		for (int j = 1; j < N - 1; j++) {
			if (visited[i][j])continue;
			int sum = checkFlower(i, j);
			if (sum != -1) {
				dfs(i, j, counter + 1, cost + sum);
				resetBoard(i, j);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			cin >> board[i][j];
	}

	
	for (int i = 1; i < N - 1; i++) {
		for (int j = 1; j < N - 1; j++) {
			int sum = checkFlower(i, j);
			dfs(i, j, 1, sum);
			resetBoard(i, j);
		}
	}
	cout << result << '\n';
	return 0;
}