/* 여러 개 이어 붙인 도형있습니다. 정사각형은 겹치면 안됩니다. 도형은 모두 연결되어야 합니다. 꼭지점 끼리 연결되어야 합니다. 엔엠 하나를 적절히 놓아서 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하세요. 회전이나 대칭 가능합니다. 예를 들어 먼저 작대기 하나를 가지고 검사를 시행합니다. 그럼, 가로로 두었을떄, 4개라는 공통점이 있습니다. 그러므로 재귀로 한번 풀어보면 어떻게 풀리나요. 뎁스 4가 되면 계산되도록 실행하면 됩니다. 그런데 움직이는 위치는? 동서남북 상관없이 4가 되면 되고, 움지이는 수는 상관없이 섬만 기억하고 있으면 됩니다. 그리고 행렬 밖으로 넘어가는지 검사하면 됩니다. dfs 로 풀이가 가능합니다. 4개의 위치를 저장하고 있는 벡터가 있어야 하나요? 그렇게 처음 시작하는 위치는 상관이 없으나, 4가지를 선택했을때, 돌아오나, visit 함수가 0인 부분을 찾아가도록 합니다. */ #include <iostream> #include <algorithm> using namespace std; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; #define SIZE 501 int n, m, x, y, nx, ny; int sum, maxVal; int sum2 = 0; int map[SIZE][SIZE]; int visit[SIZE][SIZE]; void problemIn() { cin >> n >> m; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> map[i][j]; } void visit_init() { for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) visit[i][j] = 0; } /* 깊이와 섬은 유지가 되어야 합니다. 만들어지는 순서가 어떻게 되어야 하는것이지? 동동동동 동동동 엑스와이에 대해서 비지트이므로, 엔엑스엔와이가 아니라 엑스와이에 대해서 0으로 만들어야 합니다. ㅗ 모양에 대해서 서치를 못하고 있습니다. 이것을 어떻게 처리해야하는가? 십자가 모양으로 두고 가장 작은수에 대해서 빼는 것으로 처리하도록 하겠습니다. */ // 별 모양을 제외한 가장 큰 합을 찾는 함수 void dfs(int depth, int sum, int x, int y) { visit[x][y] = 1; sum += map[x][y]; if (depth == 4) { maxVal = max(maxVal, sum); visit[x][y] = 0; return; } for (int i = 0; i < 4; i++) { nx = x + dx[i]; ny = y + dy[i]; if (nx >= 0 && ny >= 0 && nx < n && ny < m) { if (visit[nx][ny] == 0) { dfs(depth + 1, sum, nx, ny); } } } visit[x][y] = 0; } /* 벗어나더라도 어차피, 0을 더하는 숫자라서 안커질 것 같은데? 오께이. */ void star_func(int a, int b) { sum2 = 0; int x, y, minVal=1000000000; x = a; y = b; sum2 += map[x][y]; for (int i = 0; i < 4; i++) { nx = x + dx[i]; ny = y + dy[i]; if (nx < 0 || ny < 0 || nx >= n || ny >= m) { // 행렬을 벗어나면 0 처리하도록 합니다. map[nx][ny] = 0; } if (map[nx][ny] < minVal) minVal = map[nx][ny]; // 주변 4개중에 가장 작은 수 하나 저장 sum2 += map[nx][ny]; } sum2 -= minVal; } int main(void) { problemIn(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { dfs(1, 0, i, j); } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { star_func(i, j); if (maxVal < sum2) maxVal = sum2; } } cout << maxVal << endl; return 0; } |
오께이 dfs 와 예외처리에 대해서 풀었습니다. 행렬에서 4개의 선이 연결하여 depth 로 정하고, 그것들의 합을. 그래서 깊이, 합, 엑스, 와이 좌표에 대해서 기억하고 이것을 풀어주는 방식으로 하였습니다. 그리고 별모양에 대해서는 따로 풀이하기 위해서 새로운 함수를 만들었습니다. 행렬 i,j 에 대해서 겹치는 모양이 여러번 발생합니다만, 이것들을 전부 처리하는 방법은 아직 생각해내지 못했고, 그렇지 않더라도 문제는 풀리기 때문에 이대로 두었습니다. 오께이 그럼 주사위 문제로 넘어가도록 하겠습니다. 와우 이 문제를 풀다니 정말 대단..!! dfs 에서 visit를 사용 bfs 에서도 visit 를 사용 때때로 사용하지 않아도 될때가 있습니다. 벽 세우기 문제는 사용해도 되고 안사용해도 되는데. 다른 곳에 표시를 해두므로! 아하 표시하는 것은 반드시 필요합니다. 맵이던지 비지트 행렬이라던지. |
dfs 에서 뎁스가 4가 되는 경우도 리턴이므로 비지트를 0 으로 돌려두고 마지막에 그냥 단순하게 끝날때에도 비지트를 0으로 해둡니다. |