이번에는 백준 14620번 꽃길 문제를 풀어보았습니다.
문제를 처음 봤을 때 꽃을 심을 수 있는 모든 위치를 탐색해야 하기 때문에 완전 탐색으로 해결할 수 있을 것이라 생각했습니다.
현재 위치에 꽃을 심을 수 있는지 확인한 뒤, 심을 수 있다면 꽃을 심고 다음 꽃을 배치하는 방식으로 구현하였습니다.
문제 설명
꽃 하나는 가운데와 상하좌우를 포함한 총 5칸을 차지합니다.
세 개의 꽃을 서로 겹치지 않게 심으면서 비용의 합이 최소가 되도록 해야 합니다.
꽃이 화단 밖으로 나가거나 다른 꽃과 겹치는 경우에는 심을 수 없습니다.
풀이 아이디어
모든 위치에 대해 꽃을 심을 수 있는지 먼저 확인하였습니다.
꽃을 심을 수 있다면 해당 위치를 방문 처리하고 비용을 계산하였습니다.
이후 DFS를 이용하여 다음 꽃을 배치하였습니다.
재귀가 종료되면 꽃을 다시 제거하여 다른 경우를 탐색하도록 백트래킹을 수행하였습니다.
꽃 세 개를 모두 심은 경우 현재 비용과 최솟값을 비교하여 갱신하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int N;
int isplanted[10][10];
int inp_map[10][10];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};
int ret = INT_MAX;
bool canPlant(int y, int x) {
for (int k = 0; k < 4; k++) {
int vy = y + dy[k];
int vx = x + dx[k];
if (0 > vy || vy >= N || 0 > vx || vx >= N || isplanted[vy][vx]) {
return false;
}
}
return true;
}
int plant(int y, int x) {
int cost = inp_map[y][x];
for (int k = 0; k < 4; k++) {
int vy = y + dy[k];
int vx = x + dx[k];
isplanted[vy][vx] = 1;
cost += inp_map[vy][vx];
}
return cost;
}
void unplant(int y, int x) {
for (int k = 0; k < 4; k++) {
int vy = y + dy[k];
int vx = x + dx[k];
isplanted[vy][vx] = 0;
}
}
void dfs(int cost, int cnt) {
if (cnt == 3) {
ret = min(ret, cost);
}
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
if (canPlant(i, j)) {
int next_cost = cost + plant(i, j);
dfs(next_cost, cnt + 1);
unplant(i, j);
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> inp_map[i][j];
}
}
dfs(0,0);
cout << ret << '\n';
return 0;
}풀이 흐름
- 화단의 가격 정보를 입력받습니다.
- 모든 위치에 대해 꽃을 심을 수 있는지 확인합니다.
- 심을 수 있다면 꽃을 심고 비용을 계산합니다.
- DFS를 수행하여 다음 꽃을 배치합니다.
- 꽃 세 개를 모두 심은 경우 최솟값을 갱신합니다.
- 탐색이 끝나면 꽃을 제거하고 다른 경우를 탐색합니다.
- 모든 탐색이 끝난 뒤 최소 비용을 출력합니다.
구현 포인트
1. 꽃을 심을 수 있는 위치 확인
꽃잎이 화단 밖으로 나가거나 다른 꽃과 겹치는 경우에는 심을 수 없습니다.
bool canPlant(int y, int x)상하좌우 네 방향을 확인하여 범위를 벗어나거나 이미 꽃이 심어져 있는 경우에는 false를 반환하였습니다.
if (0 > vy || vy >= N || 0 > vx || vx >= N || isplanted[vy][vx]) {
return false;
}2. 꽃 심기
꽃을 심을 수 있다면 비용을 계산하고 꽃잎 위치를 방문 처리하였습니다.
int cost = inp_map[y][x];상하좌우 위치를 모두 방문 처리하면서 비용을 더하였습니다.
isplanted[vy][vx] = 1;
cost += inp_map[vy][vx];계산한 비용을 반환하여 다음 DFS에서 사용하였습니다.
3. 꽃 제거
백트래킹을 위해 탐색이 끝난 뒤에는 다시 꽃을 제거하였습니다.
void unplant(int y, int x)심었던 위치들을 다시 방문하지 않은 상태로 되돌렸습니다.
isplanted[vy][vx] = 0;4. DFS를 이용한 모든 경우 탐색
꽃을 심을 수 있는 위치를 찾으면 비용을 계산한 뒤 다음 꽃을 배치하였습니다.
int next_cost = cost + plant(i, j);
dfs(next_cost, cnt + 1);
unplant(i, j);현재 꽃을 심고, 탐색이 끝나면 다시 제거하는 방식으로 모든 경우를 탐색하였습니다.
5. 꽃 세 개를 모두 심은 경우
꽃 세 개를 모두 심었다면 현재 비용과 최솟값을 비교하였습니다.
if (cnt == 3) {
ret = min(ret, cost);
}모든 경우를 탐색한 뒤 가장 작은 비용을 정답으로 사용하였습니다.
