[9주차_금요일] 꽃길

[Jewan1120]

• 사이트 : 백준(BOJ)
• 문제: 꽃길
• 번호: 14620

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

### 💡 풀이 아이디어

[KodaHye]

🤔 시간복잡도 고려사항

• 7 ≤ 화단 한 변의 길이 ≤ 10
• 0 ≤ 지점당 가격 ≤ 200
• 꽃의 개수: 3
• 화단의 최대 개수는 100개이므로 씨앗을 심는 모든 경우의 수를 고려해도 시간 충분함 (100C3)

💡 풀이 아이디어

• 조합을 통해 씨앗을 심을 수 있는 모든 자리를 고려함
• 백트래킹을 통해 씨앗을 심고, 이후 원래 상태로 복구할 수 있도록 함
• boolean check(int r, int c): (r, c)기준 사방을 탐색했을 때, 꽃잎이 필 수 있는지 확인
• boolean isValid(int r, int c): 꽃잎이 화단의 범위를 벗어나지 않는지
• void func(int depth, int idx, int cost)
  • depth: dfs 깊이
  • idx: 몇 번째 화단에 심을 것인지에 대한 정보
  • cost: 씨앗을 심고, 꽃이 필 때 필요한 비용

[Jewan1120]

🤔 시간복잡도 고려사항

• 6 ≤ N ≤ 10
• 심어야 하는 꽃의 수: 3개
• 모든 조합을 고려하는 재귀, 백 트래킹 가능

💡 풀이 아이디어

• 유효한 범위 안에 3개의 꽃을 심어야 함 → 깊이 3의 재귀 + 백 트래킹
• 꽃을 심을 때마다 현재 위치와 상하좌우가 방문 처리가 되지 않았으면 꽃 심고 방문 처리
• 다음 깊이의 재귀 진행
• 모든 깊이마다 백 트래킹을 하여 완전 탐색을 진행

  int sum = 0;
  for (int j = 0; j < 5; j++) {
      int ny = y + dy[j];
      int nx = x + dx[j];
      visited[ny][nx] = true;
      sum += board[ny][nx];
  }
  // 다음 깊이의 재귀 진행
  recursive(depth + 1, total + sum, i + 1);
  // 방문 처리를 되돌리는 백 트래킹
  for (int j = 0; j < 5; j++) {
      int ny = y + dy[j];
      int nx = x + dx[j];
      visited[ny][nx] = false;
  }

[yeongleej]

🤔 시간복잡도 고려사항

• N≤10
• 심어야하는 꽃: 3개

=> 완전탐색 가능

💡 풀이 아이디어

• 꽃은 중심, {상하좌우}의 5평의 땅을 차지하므로 꽃술은 x:1~N-1, y=1~N-1에만 올 수 있음
• 백트래킹으로 모든 칸을 탐색하며 가능하다면 다음 꽃 심고를 진행해 3개를 모두 심으면 최솟값 비교하기
• visited를 전역변수로 두어 심은 꽃 저장하기

[baexxbin]

🤔 시간복잡도 고려사항

• 6≤N≤10
• 꽃 개수 3
• 완전탐색 가능

💡 풀이 아이디어

• 씨앗 놓을 수 있을때 하나씩 놓아보면서 3개 다놓았을때 최소값 구하기: 완전탐색
• dfs(int depth, int cur, int total)
  • depth==3, 최소 total 계산
  • 꽃 놓을 수 있는지 판단해서 다음 dfs진행
    • isEdge(r, c): 가장 자리 판단
    • !canPlant(r, c): 꽃 피는 5영역 이미 꽃이 있는지 판단
• plantSeed(int x, int y, boolean flag)
  • 꽃 5영역 flag값으로 바꾸고 비용 계산하기

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: DFS , 백트래킹
• 시간복잡도: 화단 길이 6≤N≤10 DFS 탐색 시 약 O(N*N*)소요

💡 풀이 아이디어

총 3개의 꽃을 밭에서 벗어나지 않고, 겹치지 않게 심어야 하므로 하나의 꽃(5평) 단위로 DFS 탐색을 해야함

1. 꽃을 심을 수 있는 곳 탐색
   2. 5평에 꽃 심기 (방문처리,평수마다 가격 계산)
2. 총 3개의 꽃을 심을때 까지 DFS 탐색
3. 총 3개의 꽃을 심었다면 최소 비용 계산
4. 더 적은 최소비용이 있는지 찾기 위해 꽃 하나를 없애고(방문해제) 다시 1~4번 과정 반복

[icegosimperson]

🤔 시간복잡도 고려사항

시간 복잡도 : 6<=N<=10 -> O(N^2) -> 완전 탐색가능

💡 풀이 아이디어

• 꽃 3개를 심기위한 최소 비용을 출력
• depth(현재까지 심은 꽃의 개수)가 3이 될 때까지 반복
• check : 꽃을 심을 수 있는지 (상하좌우) 확인
  • 이미 심어진 경우 false 반환
  • plant : 꽃 심으면서 비용 계산 + 방문 처리 -> cost 반환
  • backtrack : 방문 처리 되돌림