[6주차_월요일] 테트리스 블럭 안의 합 최대화 하기

[icegosimperson]

• 사이트 : 코드트리(CT)
• 문제: 테트리스 블럭 안의 합 최대화 하기
• 년도: 2017

🤔 시간복잡도 고려사항
💡 풀이 아이디어

[Jewan1120]

🤔 시간복잡도 고려사항

• 4 ≤ n, m ≤ 200 → n x m x (만들 수 있는 도형의 수)를 해도 2000ms에 가능할 듯
• 완전 탐색

💡 풀이 아이디어

• 도형의 회전, 반전을 구현하는 것보다 좌표를 미리 계산해서 배열로 만든 뒤 풀이하는 것이 구현에 빠를 것이라고 판단
• 모든 점에서 만들 수 있는 모든 도형을 만들어서 합한 후 최댓값 갱신
  • 최대를 구하는 것이기 때문에 도형을 만들 때 경계를 넘어가는 것은 따로 처리하지 않아도 된다고 생각

[KodaHye]

🤔 시간복잡도 고려사항

• map 안에서 블럭들이 위치하는 모든 경우를 고려해줘야 함
• DFS를 통해 모든 경우를 고려
  • N × M × (3 × 3 × 3) = 200 × 200 × 27

💡 풀이 아이디어

• 2중 반복문을 통해 map의 모든 지점에서 블럭을 만들 수 있는 모든 경우를 dfs를 통해 확인해 줌
• 해당 지점에서 depth가 3이 될 때까지 dfs 반복
• 현재까지의 합 + (전체 - 남은 depth 값) * map에서 최대값 <= result라면 해당 지점에서는 최대값이 될 수 없으므로 return 해주기
• T자형 블럭은 따로 처리
  • v[nr][nc] = true
  • dfs(r, c, sum + map[nr][nc], depth + 1)
• T자형 이외 나머지 블럭
  • v[nr][nc] = true
  • dfs(nr, nc, sum + map[nr][nc], depth + 1)

dfs하는 과정에서 원상복구가 되는데, 아무생각 없이 배열을 계속 초기화 하다가 메모리 초과가 발생했네요 ㅎㅎ,,!! 주의해야될 것 같습니다,,

[icegosimperson]

🤔 시간복잡도 고려사항

• n, m <=200 -> 200 200 탐색 도형(?) -> 완전 탐색

💡 풀이 아이디어

• 모든 회전할 수 있는 도형 좌표를 모두 초기화
  • (도형을 어떻게 회전할 지 고민 하고 있었는데 제완님 아이디어를 보고 저도 그렇게 했습니다.)
• 입력각 도형의 좌표를 완전 탐색

뒤집을 수 있다 조건을 놓쳐서 좌표 초기화에 어려움을 겪음 음수 좌표 생각 하기! 처음 문제를 풀 때 BFS, DFS,,? -> 어떻게 회전하지? -> ㅠㅠ -> '이거 진짜 다 구현해야하나??' 라는 생각이 들었는데, 그냥 묵묵히 구현하고 받아와도 풀리는 문제였네요,,,,ㅎㅅㅎ,,,, 끝까지 안해보는 안좋은 습관을 고쳐야겠다는 생각을 했습니다

[baexxbin]

🤔 시간복잡도 고려사항

• 4 ≤ n, m ≤ 200

  별 생각없이 시간 복잡도가 n*m이라 생각했는데, 만들 수 있는 도형의 수도 고려해야했군요..!

💡 풀이 아이디어

• dfs를 통해 깊이 4일때의 경우를 모두 구하고, 이때 최대값 갱신

• ㅜ모양과 같이 십자로 갈라지는 모양은 dfs가 불가능하기에 따로 처리

  • 깊이가 2일경우(갈라짐이 시작되는 중심), 중심점을 기준으로 dfs탐색하기

• 가지치기

  • if (mx > mx*(4-depth)+total) return; (X)
  • if (mx >(보드의 mx)*(4-depth)+total) return; (O)

    보드값에서 최대값으로해야 올바른 값이 나옴! ㅎㅎ.. 코드 더 꼼꼼히 생각해서 짜도록 연습하기... (다혜님 감사해용)

[yeongleej]

🤔 시간복잡도 고려사항

• 그래프 탐색 : O(200 * 200)
• 각 도형 탐색: 4 => 완전탐색 가능

💡 풀이 아이디어

• dfs로 각 도형 탐색하기
• 단, 현재 탐색 블럭이 2번째 블럭인 경우,
  • ㅏ ㅓ ㅗ ㅜ 처럼 2번째 블록에서 연결된 2개의 블록을 찾아야 하므로
  • 탐색칸을 현재에서 다시 탐색
• 그 이외의 블럭들은 다음칸 탐색

//현재 탐색 블록이 2번째칸
if(depth == 2) {
    visited[nx][ny] = true;
    dfs(x, y, depth+1, total+g[nx][ny]);
    visited[nx][ny] = false;
}

// 2번쨰 블록 이외에는 일반탐색
visited[nx][ny] = true;
dfs(nx, ny, depth+1, total+g[nx][ny]);
visited[nx][ny] = false;

• 가지치기
  • 현재까지 점수에서 그래프에서 나온 가장큰값으로만 채운다고 했을때, 결과값보다 작으면 탐색 중단

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: DFS
• 시간복잡도: 격자크기 4≤n,m≤200
  • O(n * m) 은 최대 10^4 으로 DFS 탐색 가능

💡 풀이 아이디어

• 최대 합을 찾기 위해 도형을 두었을 때 가능한 경우를 고려해야함 → DFS 알고리즘 사용
• 테트리스 블록의 형태가 다양해도 회전에 상관없이, 각 블록은 한 번의 움직임(상하좌우)으로 도형의 길이인 4개의 칸을 덮을 수 있음 (ㅏㅗㅜㅓ 제외)
• ㅏㅗㅜㅓ 도형은 dfs 탐색 시 방향이 중복되기 때문에 별도로 계산이 필요함
  • dfs 탐색에서 ㅏㅗㅜㅓ 칸 2개 선택 시 현재 위치에서 다시 탐색 시작

    if(depth == 2){
      dfs(depth+1, x,y,sum+block[nx][ny]);
    }

    문제에서 DFS를 떠올리지 못한 이유? 도형마다 형태가 제각각인데 어떤 방향으로 움직이고, 움직인 방향이 도형의 형태가 됐는지, 모든 도형에 적합할 수 있는지 아이디어를 떠올리지 못했음😭💦😭💦

[yeahdy]

@KodaHye ㅏㅗㅜㅓ 도형의 최댓값만 구하는 메소드에 대한 풀이 참고