반응형
728x170
이것도 정말 구현문제로써
시키는대로 하면 된다.
다만 어떻게 구현할까? 의 선택지에서
DFS를 골랐다면 고생을 덜 할 것이었다
https://www.acmicpc.net/problem/14500
#맞는 풀이
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int N,M;
int map[500][500];
bool visited[500][500];
// 멍청했따.. 어차피 4칸을 사용하는 건데... DFS로 풀었으면 되었다는 힌트를 듣고.. 현타온다.
//즉 DFS로 4칸 탐색하는 과정에 일자 모양도 있고 네모도있고 기역자도 있다.
//다만 ㅗ 모양만 DFS로 탐색은 불가능하다.
int DFS(int x, int y, int cnt){
//4개 탐색하면 종료. 4번쨰 노드 값 반환
if(cnt == 4){
return map[x][y];
}
int sum = 0;
for(int dir = 0; dir<4; dir++){
int nx = x + dx[dir];
int ny = y + dy[dir];
if(nx<0 || nx>=N || ny<0 || ny>= M) continue;
if(visited[nx][ny] != 0 )continue;
//4가지 방향으로 다 DFS 진행시켜봄
visited[nx][ny] = true;
sum = max(sum, map[x][y] + DFS(nx, ny, cnt + 1)); //4개 탐색한 것들의 결과 중에 가장 큰 값 -> sum
visited[nx][ny] = false;
//해당 방향으로 DFS가 끝났으면 다른 경로를 탐색하기 위해 false를 해줘야 한다. 백트래킹하고 비슷
}
return sum;
}
//ㅗ 모양
//DFS로 판별할 수 없는 테트로미노
int hshape(int x, int y)
{
int result = 0;
//ㅗ (현재 좌표 ㅡ의 가운데)
if (x >= 1 && y >= 1 && y < M - 1)
result = max(result, map[x][y - 1] + map[x][y] + map[x - 1][y] + map[x][y + 1]);
//ㅏ (현재 좌표 ㅣ의 가운데)
if (x >= 1 && x < N - 1 && y < M - 1)
result = max(result, map[x - 1][y] + map[x][y] + map[x][y + 1] + map[x + 1][y]);
//ㅜ (현재 좌표 ㅡ의 가운데)
if (x >= 0 && x < N - 1 && y < M - 1)
result = max(result, map[x][y - 1] + map[x][y] + map[x + 1][y] + map[x][y + 1]);
//ㅓ (현재 좌표 ㅣ의 가운데)
if (x >= 1 && x < N - 1 && y >= 1)
result = max(result, map[x - 1][y] + map[x][y] + map[x][y - 1] + map[x + 1][y]);
return result;
}
int main(){
cin >> N >> M;
for(int i = 0; i<N; i++){
for(int j = 0; j<M; j++){
cin >> map[i][j];
}
}
int result = 0;
//모든 좌표에 대해 수행
for(int i=0; i<N; i++){
for (int j = 0; j<M; j++)
{
visited[i][j] = true; //기준좌표 방문
result = max(result, DFS(i, j, 1));
result = max(result, hshape(i, j));
visited[i][j] = false; //해당 좌표 미방문 처리해줘야함.
}
}
cout << result;
return 0;
}
어차피 4칸을 탐색하는 경우에서
저런 경우가 다 나오더라
ㅗ 모양만 제외하면 DFS 4칸 탐색 경로가 곧 저 모양이더라.
근데 나는 각 방향에 대해 다 하나하나.. 하고있어서 시간이 걸렸다.
728x90
반응형
그리드형
'문제풀이(Problem Solving)' 카테고리의 다른 글
백준, BOJ, 1916번, 최소비용 : C++ [CPP] ★★★ (0) | 2021.12.22 |
---|---|
백준, BOJ, 9465번, 스티커: C++ [CPP] (0) | 2021.12.17 |
백준, BOJ, 21608번, 상어초등학교: C++ [CPP] (0) | 2021.12.08 |
백준, BOJ, 20055번, 컨베이어 벨트 위의 로봇 : C++ [CPP] (0) | 2021.12.08 |
백준, BOJ, 3190번, 뱀 : C++ [CPP] (0) | 2021.12.08 |