https://www.acmicpc.net/problem/2573
1. 의사코드
일단 분할정복으로 문제를 나눈다
1. 뺄셈할 값을 계산하기
2. 원본배열에 더하기
3. 구역세기
위 1,2,3을 year에 대해 반복하기!
2. 시행착오
1. 매year(tc)마다 vis, b배열을 초기화 해주어야 한다!
2. 구역세는 코드는 외울것.
3. 전체코드
#include <bits/stdc++.h>
using namespace std;
int n,m,cy,cx;
int dy[] = { 1,0,-1,0 };
int dx[] = { 0,1,0,-1 };
int a[304][304], b[304][304]; //원본배열,계산배열
int vis[304][304];
void dfs(int y, int x) {
vis[y][x] = 1;
for (int i = 0; i < 4; ++i) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
if (vis[ny][nx]) continue; //미방문
if (a[ny][nx] == 0) continue; // 빈칸은 제외
dfs(ny, nx);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}
//0. !전체 가능한 년도에 대해!
//1. 빙하에 대해, 주변이 빈칸이면 b배열만들기
for (int year = 1; year < 300*300; ++year) {
//배열초기화 항상 까먹지말것!
fill(&vis[0][0], &vis[0][0] + 304 * 304, 0);
fill(&b[0][0], &b[0][0] + 304 * 304, 0);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (a[i][j] == 0) continue; //빙하아니면 탐색안함
int tmp = 0;
for (int k = 0; k < 4; ++k) {
int ny = i + dy[k];
int nx = j + dx[k];
if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
if (a[ny][nx] == 0) tmp++;
}
b[i][j] -= tmp;
}
}
//2. 원본배열에 뺄셈하기
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
a[i][j] += b[i][j];
if (a[i][j] < 0) a[i][j] = 0;
}
}
//3. 빙산 덩어리 갯수 카운팅
int ret = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (a[i][j] <= 0) continue;
if (vis[i][j]) continue;
dfs(i, j);
ret++;
if (ret >= 2) { //2덩어리 이상이면 끝
cout << year;
return 0;
}
}
}
if (ret == 0) { //빙산이 분리불가능한경우 0출력(전부 0이면 bfs안돌겠지)
cout << 0;
return 0;
}
}
cout << 0;
return 0;
}
'Algorithm > dfs' 카테고리의 다른 글
백준 14888 연산자끼워넣기 c++ // dfs (0) | 2024.03.20 |
---|---|
백준 14889 스타트와링크 c++ // dfs, 사람기준으로 생각하라. 일단 모든경우의수를 벌려놓고 생각하라 (0) | 2024.03.20 |
프로그래머스 소수찾기 c++ // 순열 3P1+3P2+3P3 하는방법, 소수판별함수, dfs (0) | 2023.12.04 |
프로그래머스 미로탈출명령어 c++ // dfs 가지치기 방법, dfs중복방문 방법, dfs 시간복잡도 계산방법 (0) | 2023.12.02 |
백준 1759 암호만들기 c++ // 포함불포함 완탐 dfs, 순열시간초과 나는경우 해결 (0) | 2023.11.26 |