Machineboy空
14620 : 꽃길 - dfs 본문
https://www.acmicpc.net/problem/14620
14620번: 꽃길
2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므
www.acmicpc.net
문제요약
상하좌우로 피는 꽃 세 송이를 최소 비용으로 심기
난이도
Silver 2
풀이 포인트
- dfs 응용
REVIEW
무조건 풀 수 있을 것 같은데 안 풀려서 너무 답답했는데
어찌저찌 하드 코딩으로 해냈다.
CODE
#include <bits/stdc++.h>
using namespace std;
int n, a[11][11], visited[11][11];
vector<pair<int, int>> co;
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
bool dfs(int x, int y){
bool isAlive = true;
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny] == 1) {
//cout <<"꽃을 심을 수 없습니다.\n";
isAlive = false;
}
}
if(isAlive){
visited[x][y] = 1;
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
visited[nx][ny] = 1;
}
}
return isAlive;
}
int calculate(){
int ret = 0;
for(int i = 0; i < 11; i++){
for(int j = 0; j < 11; j++){
if(visited[i][j]) ret += a[i][j];
}
}
return ret;
}
int main(){
cin >> n;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> a[i][j];
co.push_back({i,j});
}
}
int mn = 20000000;
for(int i = 0; i < co.size()-2; i++){
for(int j = i + 1; j < co.size()-1; j++){
for(int k = j + 1; k < co.size(); k++){
//cout <<"꽃을 심었습니다\n";
memset(visited, 0, sizeof(visited));
if( dfs(co[i].first, co[i].second)&&
dfs(co[j].first, co[j].second)&&
dfs(co[k].first, co[k].second)){
mn = min(mn, calculate());
}
}
}
}
cout<< mn;
}
'Computer > Coding Test' 카테고리의 다른 글
1987 : 알파벳 - DFS, BFS (0) | 2024.04.02 |
---|---|
14497 : 주난의 난 - bfs, dfs (0) | 2024.04.01 |
1189: 컴백홈 - DFS (0) | 2024.03.22 |
17071: 숨바꼭질 5 (0) | 2024.03.20 |
13913 숨바꼭질 4 : bfs (1) | 2024.03.18 |