알고리즘/삼성SW역량테스트기출
[백준 14500번 - 테르로미노] C++ 풀이
Ompang
2021. 9. 19. 06:36
728x90
반응형
백준 14500번.
사용한 알고리즘
- bfs
depth 가 4로 정해져있으니 bfs 풀어야겠다는 생각이 들었다. 그리고 테스트 해보니 빠뜨린게 있었는데..! ㅜ/ㅗ/ㅓ/ㅏ 모양은 따로 값을 계산해서 최대값인지를 체크해주어야 한다.
bfs 를 위한 visited 배열을 만들었는데, 해당 배열을 dfs 함수의 인자로 넣어주니까 시간초과가 계속 나더라..(call by reference 로 해도..) 그래서 없애고 전역변수로 줬더니 맞았다. 그래도 시간이 빠듯한듯. dfs 풀면 대략 500 * 500 * 4 ^ 4 정도의 시간복잡도가 된다.
완성된 코드
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
vector<vector<int>> v;
vector<vector<bool>> visited;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int ans = 0;
void dfs(int x, int y, int depth, int result) {
if (depth == 3) {
ans = (ans < result) ? result : ans;
return;
} else {
for(int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= n || ny >= m || visited[nx][ny])
continue;
else {
visited[nx][ny] = true;
dfs(nx, ny, depth + 1, result + v[nx][ny]);
visited[nx][ny] = false;
}
}
return;
}
}
int main() {
scanf("%d %d", &n, &m);
v.assign(n + 1, vector<int>(m + 1));
visited.assign(n + 1, vector<bool>(m + 1, false));
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
scanf("%d", &v[i][j]);
}
}
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
visited[i][j] = true;
dfs(i, j, 0, v[i][j]);
visited[i][j] = false;
int temp = 0;
if (i - 1 >= 0 && i + 1 < n && j - 1 >= 0) {
temp = v[i][j] + v[i - 1][j] + v[i + 1][j] + v[i][j - 1];
if (temp > ans)
ans = temp;
}
if (i - 1 >= 0 && i + 1 < n && j + 1 < m) {
temp = v[i][j] + v[i - 1][j] + v[i + 1][j] + v[i][j + 1];
if (temp > ans)
ans = temp;
}
if (i - 1 >= 0 && j + 1 < m && j - 1 >= 0) {
temp = v[i][j] + v[i - 1][j] + v[i][j - 1] + v[i][j + 1];
if (temp > ans)
ans = temp;
}
if (i + 1 < n && j + 1 < m && j - 1 >= 0) {
temp = v[i][j] + v[i + 1][j] + v[i][j - 1] + v[i][j + 1];
if (temp > ans)
ans = temp;
}
}
}
printf("%d\n",ans);
}
728x90