[2주차_월요일] 예술성

[baexxbin]

• 사이트 : 코드트리(CT)
• 문제: 예술성
• 년도: 2022년

[Jewan1120]

🤔 시간복잡도 고려사항

• 구현 문제 + 완전 탐색이라 따로 고려하지 않았음

💡 풀이 아이디어

1. BFS를 진행하여 그룹을 만들어서 그룹의 번호와 개수를 저장
2. 합을 구할 때는 문제에 나와있는 식이 아니라 현재값 기준 아래 or 오른쪽이 다른 그룹인 경우 합 계산
3. 회전 구현할 때는 임시 공간에 집어넣은 후 스와핑

[yeongleej]

🤔 시간복잡도 고려사항

시뮬레이션 문제, 특이사항 X

💡 풀이 아이디어

• 예술점수 구하기 : BFS로 그룹과 인접 그룹 찾아 계산
• 정사각형 회전 : (x, y) -> (y, 정사각형크기-1-x) : 정사각형이 4개가 생기는데, 각 정사각형의 시작점을 (0,0)으로 옮긴 뒤 회전 처리하고 다시 원래 위치로 복귀

      int size = N / 2;
      for(int i=sx; i<sx+size; i++){
          for(int j=sy; j<sy+size; j++){
              // (0, 0)으로 옮겨주기
              int ox = i-sx;
              int oy = j-sy;
              // x, y -> y, size-1-x
              int rx = oy;
              int ry = size-1-ox;
              nb[rx+sx][ry+sy] = board[i][j];
          }
      }

[baexxbin]

🤔 시간복잡도 고려사항

• bfs()*4 이므로 주어진 조건 내 가능

💡 풀이 아이디어

• bfs를 이용해 그룹 별로 나누기
  • 이때 그룹간 경계선 또한 같이 구함
• 구한 그룹 정보를 바탕으로 예술점수 구하기
• 십자 회전, 부분 사각형 회전 진행

[KodaHye]

🤔 시간복잡도 고려사항

• 실행해야 되는 총 횟수: 4,
• 3 <= n <= 29
• BFS → O(RC) (2차원 배열이므로)
• 시간 충분

💡 풀이 아이디어

• BFS를 통해 특정 영역의 idx, 크기, 맞닿아 있는 구간의 개수를 구함 (HashMap에 저장)
• 배열 돌리기
  • 임시 배열 생성 후, 회전했을 때의 값 넣어주기

(뭣모르고 제완님이 비트연산해서 입력받는거 따라하다가 입력이 잘못돼서 좀 헤맸네여 ㅎ ㅠ)

[icegosimperson]

🤔 시간복잡도 고려사항 N <=29, 시간 제한 1000ms (= 1초) 4 * O(N^2) = O(N^2) 29^29 < 1억 -> 가능

💡 풀이 아이디어

• DFS를 통해 인접한 칸 중 숫자가 동일하면서 방문한 적이 없는 칸으로만 이동
• DFS 사용한 이유 : N<=29으로 크지 않아서
• 십자 반시계 방향 회전 : 가로줄 <-> 세로줄
• 4개 정사각형 시계 방향 회전 : (x, y) <-> (y, N-1-x)

[yeahdy]

🤔 시간복잡도 고려사항 알고리즘: 일반 구현 및 BFS 시간복잡도: 3 ≤ n ≤ 29

💡 풀이 아이디어

• 각 그룹 별 갯수 HashMap 으로 입력값 초기화 시 갯수도 함께 카운팅

• 다른 그룹과 맞닿은 변의 수 구하기 BFS 사용 (아직 문제 풀이중..)

• 십자모양 반시계 방향으로 회전

• 정사각형 반시계 방향으로 회전 변환을 위한 추가 배열 생성

  for(int i=0; i< ROW; i++){
  for(int j=0; j< COL; j++){
      rotated[COL-1-j][i] = origin[i][j];
  }
  }