[4주차_월요일] 토스트 계란틀

[yeahdy]

• 사이트 : 코드트리(CT)
• 문제: 토스트 계란틀
• 년도: 2018년

[yeongleej]

🤔 시간복잡도 고려사항

• N <= 50
• BFS 탐색: O(N ^ 2)
• 최대 이동횟수: 2000
• 약 2000 * O(N ^ 2)으로 가능

💡 풀이 아이디어

• bfs 탐색으로 서로 합쳐질 계란 리스트를 구하기
  • 주의) 구한 계란 리스트의 크기가 1이면 이동할 필요가 없는 계란이므로 이동 리스트에 추가 X
• 풀이 단계를 구조화하기

  1. 검사하기: 이동이 필요한 계란들이 존재하는지 여부 체크
  2. 합칠 계란 덩어리들 구하기: bfs 탐색으로 서로 합쳐져야 하는 계란리스트 구하기
  3. 합치기

[baexxbin]

🤔 시간복잡도 고려사항

• 1 ≤ n ≤ 50
• 계란의 이동이 발생하는 총 횟수는 2000번보다 작다고 가정해도 좋음 (문제 조건)
• 시간복잡도 크게 고려하지 않아도 됨

💡 풀이 아이디어

• bfs이용
  • 조건에 따라 합칠 계란들: bfs시 같은 영역에 해당
  • bfs를 돌리며 합칠 계란들에 대한 영역표시 진행(visited배열)
  • 각 bfs 결과값으로 (해당 영역의 모든 계란 합 / 해당 영역의 계란 수) 반환
• 계란 이동 여부 확인(while문 탈출 조건)
  • bfs 결과값이 현재 계란영역 값(board[i][j])와 같으면 이동이 일어나지 않은 것
  • 이동이 일어나지 않은 경우 flag++
  • flag==N*N, 모든 영역이 이동이 일어나지 않으면 탈출
  • 이동한 계란 분할
  • visited배열: 해당 계란 영역의 Idx표시
  • split배열: idx에 해당하는 분리한 계란 값 표시
  • 현재 계란의 idx에 해당하는 분리 후 계란 값으로 업데이트
  • board[i][j] = split[visited[i][j]];

무한루프 탈출 조건을 잘 설정하자!

[icegosimperson]

🤔 시간복잡도 고려사항 n<= 50, n*n = 250 BFS O(N^2)로 구현

💡 풀이 아이디어

• 문제에서 구하는 것 : 인접한 계란틀의 계란 수가 L 이상 R 이하일 때, 계란의 이동 횟수
• 4방향 원소 비교 -> Queue 이용 => Queue, ArrayList 사용한 BFS

1. 조건 확인 후 그룹 형성 :L <= 두 계란 틀 <= R조건을 만족하는 계란들을 BFS로 묶음
2. 계란 합, 평균 계산 : 조건을 만족하는 인접한 계란 양의 합을 구하고 change() 함수를 통해 그룹 내 계란 틀의 계란 양을 평균값으로 재설정
3. 계란 양 재설정 : ArrayList에 저장된 모든 계란틀에 계산한 평균값 업데이트 -> 계란 이동 처리

★ 지난주 주신 피드백 반영 1) 좌표 row, column으로 설정 (오른쪽, 아래, 왼쪽, 위)

    static int[] dr = {0, 1, 0, -1};  // 행(row) 
    static int[] dc = {1, 0, -1, 0};  // 열(column) 

2) 좌표 class로 설정

 public static class Node {
        int r, c; 
        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

3) isRange 함수로 범위 체크

    private static boolean isRange(int r, int c) { // 배열의 범위를 벗어나지 않는지 확인
        return r >= 0 && r < n && c >= 0 && c < n; 
    }

Node Class 설정하는게 낯설고 어려웠습니다

[KodaHye]

🤔 시간복잡도 고려사항

• 1 <= n <= 50
• 1 <= L <= R <= 100
• 계란의 이동 총 횟수 2000

BFS(50 × 100 × 4) × 2000 < 1억 이므로 주어진대로 구현해도 됨

💡 풀이 아이디어

BFS를 통해 상, 하, 좌, 우 계란선이 분리될 수 있는지 확인 분리 이후 다시 계란틀의 계란양이 업데이트 되야하므로 BFS에 사용할 큐 외에 따로 좌표를 저장할 큐가 필요

• ArrayDeque<Point> q: BFS를 할 때 사용할 큐
• ArrayDeque<Point> tmp: 방문한 계란틀의 위치 저장할 큐
• int cnt: 계란틀의 총 개수
• int sum: 합쳐진 계란의 총 합
• boolean flag: 분리될 수 있는 계란선이 있는지 확인하는 변수
• BFS를 통해 두 계란틀의 계란 차이가 L이상 R이하가 되는지 확인
• 조건 만족한다면 tmp에 위치 저장
• cnt와 sum 업데이트
• BFS가 끝나면 tmp큐가 빌 때까지 반복하면서 방문했던 계란틀의 위치의 값을 sum / cnt로 업데이트

[Jewan1120]

🤔 시간복잡도 고려사항

• 1 ≤ n ≤ 50
• 이동이 발생하는 총 횟수는 2000보다 작다고 가정
• 50 x 50 x 2000 < 10^9 → BFS 가능

💡 풀이 아이디어

• 인접한 계란들 중 조건에 맞는 계란들만 연산 → BFS
• 순회를 하면서 다음 좌표와 비교했을 때, 계란틀을 분리해야 하는 지 확인
  • 순회를 하기 때문에 진행 방향의 좌표만 확인하면 됨 (우, 하)
• 방문하지 않은 계란들 중 분리가 가능하다면 해당 좌표를 ArrayList에 넣어 BFS가 끝난 후 역 추적 하여 계산된 값을 할당
• 합쳐진 계란은 방문처리를 하여 다음 연산에서 제외
• 해당 과정을 분리가 안 일어날 때까지 반복

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘:BFS + 구현
• 시간복잡도:
  • 계란틀 크기 1 ≤ n ≤ 50 > n*n=250
  • 계란의 이동이 발생하는 총 횟수는 2000번
  • 250*2000

💡 풀이 아이디어

• 합칠 수 있는 계란틀에 대해 BFS를 사용 해 그룹을 나누고, 같은 그룹끼리 계란틀 검사 후 결과를 똑같이 분배
  • 이 과정이 계란의 1회 이동 횟수
  • 그룹을 나눌 수 없을때 까지 반복
• 그룹을 나누는 방법?
  • 하나의 계란마다 BFS 를 탐색하면서 그룹찾기
• 같은 그룹끼리 계란틀 검사 후 다시 분배하는 방법
  • 같은 그룹끼리 List 에 담아서 계산