[7주차_월요일] 시공의 돌풍

[KodaHye]

• 사이트 : 코드트리(CT)
• 문제: 시공의 돌풍
• 년도: 2019

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

[KodaHye]

🤔 시간복잡도 고려사항

• 6 <= n, m <= 50
• 1 <= t <= 1,000 50 50 1,000 < 1억이므로 주어진대로 구현해도 시간이 충분

💡 풀이 아이디어

• int[][] map: 먼지량을 저장하는 배열
• Sigong[] sigong: 시공의 돌풍 위치를 저장하기 위한 배열
• step1(): 먼지가 인접한 4방향으로 확산
  • int[][] tmp: 좌표별 먼지의 변화량을 저장하는 변수
    1. 배열의 모든 위치를 확인하며 tmp의 값을 설정해줌
    2. tmp 값을 설정해준 이후, map의 먼지량 갱신
• step2(): 시공의 돌풍 청소
  • sigong[0]과 sigong[1]의 경우를 나누어서 생각
  • 움직일 방향, 움직이는 방향을 변경할 방향
  • idx: 0
    • 움직일 방향: 상, 우, 하, 좌 (시계방향)
  • idx: 1
    • 움직일 방향: 하, 우, 상, 좌 (반시계방향)
  • 시공의 돌풍을 시작점으로 기준으로 다음 좌표 확인
  • 다음 좌표 값을 현재 좌표 값으로 갱신해줌
• getSum()
  • map을 확인하며 먼지의 총 합계 구하기

[Jewan1120]

🤔 시간복잡도 고려사항

• 6 ≤ n, m ≤ 50 이지만 시뮬레이션 문제라서 크게 신경쓰지 않음.

💡 풀이 아이디어

1. 확산 구현 spread()
   • 기존 배열의 확산하는 양에 영향을 주지 않기 위해서 변화량 배열 만들어 확산되는 양을 저장함
   • 확산이 끝났다면 기존 배열과 변화량 배열을 합하여 최종적으로 확산된 배열을 만들어 줌
2. 회전 구현 rotate()
   • 윗 회전과 아랫 회전을 따로 진행
   • 처음 회전을 시작하는 좌표에서 회전을 하여 시공의 돌풍의 좌표까지 도달했다면 회전을 멈춤
3. 총합 계산 calculate()
   • 시공의 돌풍의 값이 -1 x 2이므로 +2로 전처리를 한 후 합을 계산

[yeongleej]

🤔 시간복잡도 고려사항

• n, m ≤ 50
• t ≤ 1,000 => O(n m t) == 2,500,000 : 완전탐색 가능

💡 풀이 아이디어

1. spread(): 먼지확산

• 새로운 배열 tmp를 만들어서 확산된 먼지들을 누적해서 기록
• 4방향 탐색으로 확산 가능한 구역 리스트에 삽입후, 모든 방향 탐색 이후에 먼지 확산
• 원본배열 g를 축적된 임시 배열 tmp로 바꿔주기

2. clean(): 돌풍 청소

• 윗칸: 회전방향은 반시계방향이지만, 움직이는 방향은 시계방향
  • {상, 우, 하, 좌} 순으로 움직이기
• 아랫칸: 회전방향은 시계방향이지만, 움직이는 방향은 반시계방향
  • {하, 우, 상, 좌} 순으로 움직이기
• 4방향을 모두 회전했다면 break
• 시작점이 돌풍이었으므로 원래대로 돌풍으로 바꾸고
• 돌풍의 우측 옆칸은 0으로 변경

[baexxbin]

🤔 시간복잡도 고려사항

• 6 <= n, m <= 50
• 1 <= t <= 1,000
• 50501000, 완전탐색 가능

💡 풀이 아이디어

1. 먼지 확산 (diffusion())

   • 전체 먼지 돌면서 조건에 맞게 먼지 확산
   • dust배열을 둬서 확산된 먼지들 저장 후, 모든 먼지가 다 돈 후 기존 배열에 dust값 더하기

2. 청소기 실행 (cleanUp(), cleanDown())

   • 각 청소기의 흐름대로 큐에 먼지들 넣어줌
   • 큐에서 먼지를 빼면서 먼지들 한칸씩 이동
   • cleanUp(): (R,0) -> (R,M) -> (0,M) -> (0,0) -> (0,0)
   • cleanDown(): (R,0) -> (R,M) -> (N,M) -> (N,0) -> (R,0)
   • 이때 꼭짓점 좌표들 겹치지 않도록 주의
   • 맨처음 청소기 바람 0 넣기, 청소 다 끝난 후 청소기 -1 표시

[icegosimperson]

🤔 시간복잡도 고려사항

6 ≤ n, m ≤ 50 -> 주어진 시간 내 구현 가능

💡 풀이 아이디어

1. 먼지 확산 spread()
   • 각 칸에 먼지가 인접한 4방향 (상하좌우)로 확산
   • 확산된 먼지 양 = (해당칸의 먼지 양) / 5
   • 확산된 먼지를 임시 배열temp에 저장 -> 확산 -> 원래 배열에 반영
2. 시공의 돌풍 clean()
   • 시공의 돌풍 위치(윗부분, 아랫부분)를 clean 함수에 반복문으로 구현
   • 윗부분(반시계 방향)
   • (i, 0) -> (i-1, 0) 아래에서 위로 이동
   • (0, i) -> (0, i+1) 왼쪽에서 오른쪽으로 이동
   • (i, m-1) -> (i+1, m-1) 위에서 아래로 이동
   • (top, i) -> (top, i-1) 오른쪽에서 왼쪽으로 이동
   • 아랫부분 (시계 방향)
   • (i, 0) -> (i+1, 0) 위에서 아래로 이동
   • (n-1, i) -> (n-1, i+1) 왼쪽에서 오른쪽으로 이동
   • (i, m-1) -> (i-1, m-1) 아래에서 위로 이동
   • (bottom, i) -> (bottom, i-1) 오른쪽에서 왼쪽으로 이동

[yeahdy]

🤔 시간복잡도 고려사항

• 시간복잡도: BFS + 구현
• 알고리즘: 격자크기 6 ≤ n, m ≤ 50 폭풍 횟수 1 ≤ t ≤ 1,000 BFS 알고리즘으로 구현할 경우 O(n*m*t*4) > 10^6

💡 풀이 아이디어

• bfs(int n, int m) BFS 너비 탐색을 통해 확산된 먼지 계산하기
• goTornado(int n, int m, int[] tornado) 문제 요구사항 대로 윗면,아랫면을 나눠서 시공의 돌풍이 청소하기
  • 윗면/아랫면 각각 아랫줄,왼쪽줄,윗줄,오른쪽줄 순회하면서 먼지 이동 시키기