<Baekjoon> #14500 DFS_테트로미노 c++
처음에는 문제를 보고 모든 테트로미노의 모양을 구해야 하는 아이디어밖에 떠오르지 않았다. 그래서 다른 사람들의 풀이를 많이 참고했다.
(실제로 어떤 사람은 모든 경우의 수를 구한 사람도 보았다)
먼저 테트로미노를 보면 ㅜ 이 모양 이외에는 깊이가 4인 모양임을 알 수 있다 (테트로미노를 대칭시키고 회전을 시킬 수 있다고 했으므로)
- DFS 함수
DFS 함수의 파라미터로는int y, int x, int depth, int sum
를 둔다.y,x
는 모든 정점에서 DFS를 구하기 위함이고depth
와sum
은depth=4
에 이르렀을 때,sum
과maxSum
을 비교하여maxSum
을 구하기 위함이다.
- 모든 정점에서 DFS를 구한다
for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { visited[i][j] = true; ---DFS 함수 호출--- visited[i][j] = false; ---DFS로 구할 수 없는 ㅜ 모양--- } }
//DFS 함수 내 int dy[4] = { -1,0,1,0 }; int dx[4] = { 0,1,0,-1 }; for (int i = 0; i < 4; i++) { int nx_y = y + dy[i]; int nx_x = x + dx[i]; ..... }
- ㅜ 모양을 구하는 함수
void extraordinaryShape(int y, int x)
함수 내에서 ㅏ,ㅓ,ㅗ,ㅜ 의 모양일 때 maxSum을 구하는 경우를 작성
전체코드
#include <iostream> #include <algorithm> #include <string.h> using namespace std; const int MAX = 501; int dy[4] = { -1,0,1,0 }; int dx[4] = { 0,1,0,-1 }; int n, m; int tetro[MAX][MAX]; bool visited[MAX][MAX]; int maxSum = -0x7fffffff; void dfs(int y, int x, int depth, int sum) { if (depth == 4) { maxSum = max(sum, maxSum); return; } for (int i = 0; i < 4; i++) { int nx_y = y + dy[i]; int nx_x = x + dx[i]; if (nx_y<0 || nx_x<0 || nx_y>=n || nx_x>=m) continue; if (!visited[nx_y][nx_x]) { visited[nx_y][nx_x] = true; dfs(nx_y, nx_x, depth + 1, sum + tetro[nx_y][nx_x]); visited[nx_y][nx_x] = false; } } } void extraordinaryShape(int y, int x) { int sum = 0; //ㅏ if (y+2<n && x+1<m) { sum = tetro[y][x] + tetro[y + 1][x] + tetro[y + 1][x + 1] + tetro[y + 2][x]; maxSum = max(maxSum, sum); } //ㅗ if (y-1>=0 && x+2<m ) { sum = tetro[y][x] + tetro[y][x+1] + tetro[y][x +2] + tetro[y-1 ][x+1]; maxSum = max(maxSum, sum); } //ㅓ if (y-1>=0 && y+1 <n && x+1 <m) { sum = tetro[y][x] + tetro[y ][x+1] + tetro[y -1][x + 1] + tetro[y +1][x+1]; maxSum = max(maxSum, sum); } //ㅜ if (y+1<n && x+2<m) { sum = tetro[y][x] + tetro[y][x+1] + tetro[y][x + 2] + tetro[y+1][x+1]; maxSum = max(maxSum, sum); } } int main() { memset(visited, false, sizeof(visited)); cin >> n >> m; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> tetro[i][j]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { visited[i][j] = true; dfs(i, j, 1, tetro[i][j]); visited[i][j] = false; extraordinaryShape(i, j); } } cout << maxSum << endl; return 0 ; }
Author And Source
이 문제에 관하여(<Baekjoon> #14500 DFS_테트로미노 c++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmy/Baekjoon-14500-DFS테트로미노-c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)