오랜만에 다시 풀어보는 DFS + 시뮬레이션 형식의 문제이다. 솔직히 문제를 처음 읽었을때 너무나도 어려운 문제를 예상 했었다. 문제 내용은 해당 모양의 도형을 Matrix 에서 찾은 후에 그 도형안에 있는 숫자의 최대합을 구하는 문제였고, 도형은 회전, 그리고 대칭 또한 가능했기 때문이다. 이런 류의 문제는 예전에 군대 있었을때 GP 에서도 풀어봤던 기억이 있었는데 정말로 너무 어렵고 복잡하고 코드 또한 굉장히 많이 써야지 작동이 되는 코드이다. 그렇기 때문에 문제를 읽은 순간부터 너무 힘들거라는 생각이 들었고 어떻게 풀어야할지 고민이 들던 와중에 좀 더 쉬운 방법이 있단걸 깨달았다.
테트로미노 라는 도형 목록중에 가장 마지막 도형을 제외하면 일반적인 dfs 형식의 탐색으로도 탐색 가능한 범위 였다. 이유로는 모드 3번째까지의 깊이까지 갔을때 상하좌우로만 움직여준 다는 가정이 있다면은 저 모양들은 전부 만들수있었다. 그리고 이거는 DFS 에 대한 이해도가 좀 더 깊다면 그림으로 그렸을때 설명이 됐었다.
문제는 저 마지막 도형만 다뤄줘야 한다는것이였는데, 마지막 도형을 돌린 모습을 전부 좌표에다가 담고 비교를 하면 모든 도형에 대한 값이 나올수 있기때문에 그걸 이용해서 answer 값을 업데이트 해주면 끝나는 문제이다.
항상 visited 벡터는 초기화를 시켜줘야한다.
이거는 내가 항상 쓰던 DFS 함수에 표본이었다. 그런데 이 DFS 를 쓰면은 계속 답이 다른값이 나왔는데, 내가 깨달은거는 나는 한 좌표에서 여러가지 테트로미노의 도형을 확인 해야하기때문에 visited 벡터의 방문 여부를 계속 업데이트 시켜줬어야했다. 그러나 이 DFS 같은 경우는 보통 "범위 탐색" 에 많이 쓰이는 함수이기 때문에 실패를 했었다.
새롭게 고친 DFS 였고, 마치 내가 BFS를 할때처럼 썼지만, 특정한 여러가지 모양의 탐색을 할때는 이런 류의 DFS 가 훨씬 더 효율적이라는 것을 배웠던거같다.
DFS로 탐색이 불가능한 도형같은 경우 좌표를 이렇게 하나씩 입력해주었는데 마지막에 돌아가는 ㅏ 모양의 테트로미노를 내가 잘못계산해서 너무 많은 시간을 보낸거때문에 화가 난다. 그래도 잘 고쳐서 답이 나와서 정말 다행이라고 생각했다.
#include <iostream>
#include <bits/stdc++.h>
#define endl "\n"
#define MAX 100010
using namespace std;
int N, M;
bool visited[500][500];
int matrix[500][500];
int answer = 0;
vector<pair<int,int>> dir = {{0,1},{0,-1},{1,0},{-1,0}};
void Input(){
cin >> N >> M;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cin >> matrix[i][j];
}
}
}
// void dfs(int i, int j, int cnt, int curr_total){
// if(i < 0 || j < 0 || i >= N || j >= M || visited[i][j] == true || cnt > 3) return;
// if(cnt == 3){
// answer = max(answer,curr_total);
// return;
// }
// visited[i][j] = true;
// dfs(i+1,j,cnt+1,curr_total + matrix[i][j]);
// dfs(i-1,j,cnt+1,curr_total + matrix[i][j]);
// dfs(i,j+1,cnt+1,curr_total + matrix[i][j]);
// dfs(i,j-1,cnt+1,curr_total + matrix[i][j]);
// }
void dfs(int i, int j, int cnt, int curr_total){
visited[i][j] = true;
if(cnt == 3){
answer = max(answer,curr_total);
return;
}
for(pair<int,int>& p: dir){
int nX = i + p.first;
int nY = j + p.second;
if(nX < 0 || nY < 0 || nX >= N || nY >= M || visited[nX][nY] == true) continue;
dfs(nX,nY,cnt+1,curr_total + matrix[nX][nY]);
visited[nX][nY] = false;
}
}
int findShape(int i, int j){
int a = 0, b =0, c =0, d = 0;
if(i + 1 < N && j + 2 < M){
a = (matrix[i][j] + matrix[i][j+1] + matrix[i][j+2] + matrix[i+1][j+1]);
}
if(i - 1 >= 0 && j + 1 < M && i + 1 < N){
b = (matrix[i][j] + matrix[i-1][j+1] + matrix[i][j+1] + matrix[i+1][j+1]);
}
if(i - 1 >= 0 && j + 2 < M){
c = (matrix[i][j] + matrix[i-1][j+1] + matrix[i][j+1] + matrix[i][j+2]);
}
if(i + 2 < N && j + 1 < M){
d = (matrix[i][j] + matrix[i+2][j] + matrix[i+1][j] + matrix[i+1][j+1]);
}
return max({a,b,c,d});
}
void Solution(){
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
memset(visited,false,sizeof(visited));
dfs(i,j,0,matrix[i][j]);
answer = max(answer,findShape(i,j));
}
}
cout << answer;
}
void Solve(){
Input();
Solution();
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
freopen("input.txt", "r", stdin);
Solve();
return 0;
}
배운점:
1. DFS 에 활용
2. 도형 돌리기
