[3주차_금요일] 나무 타이쿤

[Jewan1120]

• 사이트 : 코드트리(CT)
• 문제: 나무 타이쿤
• 년도: 2021년

[KodaHye]

🤔 시간복잡도 고려사항

• 3 <= n <= 15
• 1 <= m <= 100
• 1 <= d <= 8

n, m, d를 고려했을 때, 문제에 주어진대로 구현해도 시간이 충분

💡 풀이 아이디어

처음에는 영양제가 있는 곳을 ArrayList<Point>로 저장해서 풀이했는데, 이후 따로 Point 클래스를 사용하지 않고, boolean tmp 배열을 사용하여 풀이함

시간, 메모리 측면에서 tmp 배열을 사용하는 것이 더 효율적이었음

• 문제에 주어진대로 move(), grow(), cutAndPut() 구현
  • move(): 특수 영양제 이동
  • grow(): 대각선 확인 후 영양제 투입
  • cutAndPut(): 높이가 2이상인 리브로수를 베고, 특수 영양제 투입
• int[][] map: 나무의 높이를 저장하는 변수
• boolean[][] check: 특수 영양제의 위치를 저장하는 변수
• boolean[][] tmp: 영양제의 위치가 갱신될 때 위치를 저장하는 임시 변수
  • 특수 영양제의 위치가 이동하는 부분과 높이가 2 이상인 나무를 자르고 새로 영양제를 투입하는 부분에서 필요
• move(int d, int p)
  • int nr = (r + dr[d] * p) % N; nr = nr < 0 ? nr + N: nr;
  • int nc = (c + dc[d] * p) % N; nc = nc < 0 ? nc + N: nc;

[yeongleej]

🤔 시간복잡도 고려사항

• n <= 15
• m <= 100
• d <= 8 => O(n n m)은 충분히 가능하므로 크게 고려하지 않아도 됨

💡 풀이 아이디어

• g[][] : 리브로수의 높이 배열

• s[][] : 특수 영양제 배열

• 문제에서 요구하는 단계별로 함수로 구조화해서 풀이

  1. 특수 영양제 이동시키기
  2. 투입 시키기 : 높이 +1
  3. 인접 대각선 확인하고 높이 증가시키기
  4. 높이 2이상인 리브로수 확인 & 영양제 생성 (기존 영양제 위치 제외)

• 영양제 이동 시키기

  • 범위를 벗어나는 경우는 반대편으로 이동해야 하므로, 모드 연산(%)과 N을 추가해줌
  • nx = (x + dx[i]*cnt + N) % N
  • ny = (y + dy[i]*cnt + N) % N

• 특수 영양제의 이동은 tmp 배열을 만들어 이동 시킨 후 s에 깊은 복사

[baexxbin]

🤔 시간복잡도 고려사항

• n <= 15
• m <= 100
• d <= 8
• 크게 시간복잡도 고려하지 않음

💡 풀이 아이디어

• 시뮬레이션으로, 단계 별 함수로 진행
• 영양제 Pills Queue로 관리

// 0. 초기 영양제 주입
(N-1,0), (N-1,1), (N-2,0), (N-2,1) 위치

// 1. 영양제 움직이기
movePill(d, p);

// 2. 리브로수 성장
growTree();

// 3. 새로운 특수 영양제 투입
injectPill();

// 4. 리브로수 높이 총 합
for문 돌면서 총 합 구함

• 영양제 움직이기 movePill(int d, int p)

  • 모듈러 연산으로 행,열 연결 구현
  • 이동거리도 모듈러 연산 진행
  • !! nx, ny 음수 예외처리 !!

• 리브로수 자라기 growTree()

  • !! 영양제 투입된 자리 먼저 자란 후! 대각선 진행!!

음수 처리랑, 영양제 위치 먼저 다 성장하지 않고 동시에 대각선을 보도록 진행했어서 어디서 틀렸나 헤맸었다ㅜ 음수 처리 조심! 그리고 시뮬레이션인 만큼 코드 동작흐름을 잘 파악해야겠다.

[icegosimperson]

🤔 시간복잡도 고려사항 단순 구현, O(N^2) 이상 가능

💡 풀이 아이디어

• 대각선 체크

  // 대각선 체크
      for(int i=0; i<N; i++){
          for (int j=0; j<N; j++){
              if(visited[i][j]){
                  for(int d=1; d<8; d+=2){ // 대각선 방향 체크(1, 3, 5, 7)
                      int nx = i + dx[d];
                      int ny = j + dy[d];
                      if(nx<0 || ny <0 || nx >=N || ny >= N){
                          continue;
                      }
                      if(map[nx][ny]>0){ // 대각선에 있으면 ++
                          map[i][j]++;
                      }
                  }
              }
          }
      }

• 새로운 영양제 위치 갱신

  // 높이가 2이상인 리브로수는 잘라냄
      for(int i=0; i<N; i++){
          for(int j=0; j<N; j++){
              if(visited[i][j]){
                  visited[i][j] = false; // 기존 영양제 없앰
              }
              else if(map[i][j] >=2){  // 높이가 2이상인 리브로수는 잘라냄
                  map[i][j] -= 2;
                  visited[i][j] = true; // 새로운 영양제 배치
              }
          }
      }

• 음수 좌표계 고려하지 못해서 지영님 아이디어를 참고했습니다

int nx = (i + dx[direction] * pace + N) % N;
int ny = (j + dy[direction] * pace + N) % N;

dx, dy 배열 설정할 때 일반 좌표평면으로 착각해서 →(1, 0) ↗(1, 1) ↑(0, 1) ↖(-1, 1) ←(-1, 0) ↙(-1, -1) ↓(0, -1) ↘(1, -1) 이런식으로 풀었었습니다ㅎ,,, 2차원배열 [y][x] 매핑 부분 다시 공부했습니다!

[Jewan1120]

🤔 시간복잡도 고려사항

• 3 ≤ n ≤ 15
• 1 ≤ m ≤ 100
• 구현 문제라서 딱히 신경쓰지 않았음

💡 풀이 아이디어

• 영양제 움직임 구현
  • 영양제의 위치는 boolean[][]으로 저장하였으며 움직임을 구현하기 위해 좌표를 큐에 넣어서 하나씩 꺼내며 진행
  • 경계선을 넘어가면 좌표를 갱신해줘야함

    int y = (cur[0] + dy[oper[0]] * oper[1] + n) % n;
    int x = (cur[1] + dx[oper[0]] * oper[1] + n) % n;

  • 영양제를 움직인 후, 해당 위치의 나무가 성장하므로 나무의 크기를 1증가
• 나무의 성장 구현
  • 영양제가 있는 나무는 대각선 방향에 존재하는 나무의 개수만큼 성장
• 나무 자르기, 영양제 투입 구현
  • 기존에 영양제가 있는 위치는 영양제 지워주기
  • 영양제가 없었던 위치에서는 크기가 2이상인 나무는 2만큼 잘라내고 영양제 투입

아침에 올린 줄 알았는데 안 올라가졌네요.. 다시 작성했습니다..😿 나무 성장 및 영양제 위치를 저장하는 방법은 새로운 배열을 만든 다음 마지막에 갱신해주는 방법이 안전한 것 같습니다