https://www.acmicpc.net/problem/14500
전형적인 DFS(깊이 우선 탐색, Depth-First Search) 문제이다.
DFS는 BFS(너비 우선 탐색, Breadth-First Search)와 구분되는데, 우선 각각의 개념을 알아보자
DFS란?
하나의 정점을 기준으로 그 지점에서 갈 수 있는 점들을 기준으로 탐색하는 방법이다.
글로 길게 적는 것보다 이에 대해 잘 설명하는 그림이 있어 들고 왔다.
출처는 https://twpower.github.io/151-bfs-dfs-basic-problem이다.
BFS란?
하나의 정점을 기준으로 그와 가까운 점들부터 탐색하는 것을 의미한다.
문제에 제시된 테트로미노의 모양을 보면 깊이 탐색을 통해서 구현이 가능하다.
하지만 단 하나 ㅜ 모양의 테트로미노는 깊이 탐색으로 구현이 불가능하다. N번째 영역에서 N+1번째 영역으로 넘어갈 때 오른쪽이나 왼쪽 인접한 곳에 붙어있어야 하는데, 그렇지 않은 것을 알 수 있다.
ㅜ 모양의 테트로미노는 따로 구현을 해줘야 한다.
#include <cstdio>
#include <utility>
using namespace std;
//input이 길 경우 파일로 넣어준다.
FILE* in = fopen("input.txt", "r");
int n, m;
int map[501][501];
bool visited[501][501];
// 디버깅용 pair 배열
// pair<int, int> path[4];
// DFS를 위한 방향 정보
int dx[4]{ 0, 0, -1, 1 };
int dy[4]{ -1, 1, 0, 0 };
int max;
//재귀함수를 통한 DFS 구현
void tetro(int x, int y, int idx, int ret) {
// 4가지를 돌면 max 값 비교
if (idx == 4)
{
if (max < ret)
max = ret;
return;
}
for (int i = 0; i < 4; i++)
{
int next_x = x + dx[i]; int next_y = y + dy[i];
// 해당 셀이 방문하지도 않고, 범위 내에 있다면
if (!visited[next_x][next_y] && next_x >= 0 && next_x < n && next_y >= 0 && next_y < m) {
// 해당 셀에 방문했다고 표시
visited[next_x][next_y] = true;
// 디버깅용 경로 탐색
// path[idx] = make_pair(x, y);
// 다음 셀로 진행
tetro(next_x, next_y, idx + 1, ret + map[x][y]);
// 반드시 next_x, next_y에 check 한 것을 없애줘야 함.
visited[next_x][next_y] = false;
}
}
}
//DFS에 해당하지 않는 것은 따로 구현해줌.
void non_dfs(int x, int y){
//ㅗ
int ret;
if (x >= 1 && y < m-2)
{
ret = map[x][y] + map[x][y+1] + map[x][y + 2] + map[x - 1][y + 1];
if (ret > max)
max = ret;
}
//ㅏ
if (x < n - 2 && y < m - 1)
{
ret = map[x][y] + map[x + 1][y] + map[x + 2][y] + map[x + 1][y + 1];
if (ret > max)
max = ret;
}
//ㅜ
if (x < n - 1 && y < m - 2)
{
ret = map[x][y] + map[x][y + 1] + map[x][y + 2] + map[x + 1][y + 1];
if (ret > max)
max = ret;
}
//ㅓ
if (x < n - 2 && y >= 1)
{
ret = map[x][y] + map[x + 1][y] + map[x + 2][y] + map[x + 1][y - 1];
if (ret > max)
max = ret;
}
}
int main() {
fscanf(in, "%d %d", &n, &m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
fscanf(in, "%d", &map[i][j]);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
visited[i][j] = true;
tetro(i, j, 0, 0);
visited[i][j] = false;
}
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
non_dfs(i, j);
printf("%d", max);
}
'알고리즘 > SW Expert Academy' 카테고리의 다른 글
[SW Expert Academy] 2115. 벌꿀 채취 C/C++ 풀이 (0) | 2020.08.09 |
---|---|
[SW Expert Academy] 2117. 홈 방범 서비스 C/C++ 풀이 (0) | 2020.08.07 |
[SW Expert Academy] 5648. 원자 소멸 시뮬레이션 C/C++ 풀이 (0) | 2020.08.05 |
[SW Expert Academy] 2382. 미생물 격리 C/C++ 풀이 (0) | 2020.08.04 |