[8주차_수요일] 떡 돌리기

[baexxbin]

• 사이트 : 백준(BOJ)
• 문제: 떡 돌리기
• 번호: 20007

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

### 💡 풀이 아이디어

[KodaHye]

🤔 시간복잡도 고려사항

• 2 <= 마을의 개수 (노드 개수) <= 1,000
• 2 <= 도로의 정보 (간선의 개수) <= 200,000

그래프 상에서 최소 거리 구하기: 다익스트라 → O(200,000(간선) × log 1,000 (노드))

💡 풀이 아이디어

• ArrayList<Node> adj[]: 인접리스트 정보 입력받기
• dijkstra(): 우선순위큐를 이용한 다익스트라 알고리즘을 통해 출발지점으로부터 떨어진 최소 거리 구하기
• long[] dis: 출발 지점으로부터 떨어진 최소 거리
• Arrays.sort(dis)후 한 번에 갈 수 있는 최대 거리인 X와 비교하며 몇 번 왔다 갔다 해야되는지 확인하기

[icegosimperson]

🤔 시간복잡도 고려사항

• 시간복잡도 : N<=1,000, M<=100,000 O(NM) 가능

💡 풀이 아이디어

• 이웃집 모두에 방문할 때까지 걸리는 최소 일을 출력
• 이웃집까지 최단거리 계산 -> Dijkstra -> PriorityQueue 최소 거리 구하기
• 최소 일수 계산

      for (int i = 0; i < N; i++) { // 거리 확인
          if (i != Y) { // 성현이의 집은 제외
              if (distance[i] * 2 > X) { // 왕복 거리 초과
                  System.out.println(-1); // 방문x
                  return;
              }
              if (totalDistance + distance[i] * 2 > X) { // 하루 이동 거리 초과한 경우
                  days++; // 하루 추가
                  totalDistance = 0; // 새로운 날로 초기화
              }
              totalDistance += distance[i] * 2; // 방문한 거리 추가
          }
      }

• 만약 모두 방문할수 없으면 -1을 출력

  개인적으로 최소 일수 계산하는게 어려웠습니다

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: 다익스트라
• 시간복잡도: 집 2 ≤ N ≤ 1,000 양방향 도로 1 ≤ M ≤ 100,000 우선순위 큐를 이용할 경우 O(logN) + 다익스트라 알고리즘 O((N+M)) = O((N+M)logN)

💡 풀이 아이디어

• 다익스트라 알고리즘 노드 간의 연결된 간선이 방향과 거리 비용을 가지고 있고, 시작노드에서 다른 노드들까지의 최단거리 비용을 구할 때 사용 A > B 이동 가능, B < A 이동불가 하지만 이 문제에서는 양방향 도로이므로 양방향 그래프로 모델링 해야함

코드	설명
List<List<Pos>> graph	양방향 그래프 (하나의 Pos 당 여러개의 노드 존재)
int[] table	각 노드 별 최단거리를 저장하는 테이블
PriorityQueue<Pos> road	다음 노드 탐색 순서를 저장 (최단거리 값을 기준으로 오름차순 정렬)
int INF = Integer.MAX_VALUE	초기값 설정을 위한 변수

• 거리가 가까운 집부터 방문

  • PriorityQueue를 사용 해 거리가 가까운 노드 기준으로 오름차순 정렬해서 거리가 가까운 집부터 탐색

• 집에서 자야 하므로 왕복할 수 없는 거리는 다음날 가기로

  • 항상 시작노드를 기준으로 다음 노드까지의 최단 거리를 계산
  • 각 노드까지의 최단거리를 모두 구하면서 최단거리 테이블을 갱신

• 하루에 X보다 먼 거리를 걷지 않고

  • 최단거리 테이블을 순회하면서 최단 거리가 X 이상이 됐을 때 날을 카운팅

[baexxbin]

🤔 시간복잡도 고려사항

• 2 ≤ N ≤ 1,000
• 1 ≤ M ≤ 100,000
• 도로의 길이: 1 ≤ C ≤ 10,000
• 우선순위 큐: O((V+E)logV), < N*M(10^8)

💡 풀이 아이디어

• 다익스트라
  • 각 이웃에게 떡을 돌릴 가장 가까운 거리: 다익스트라 (dist배열)
• 떡 돌리기 위한 최소 날짜 구하기
  • 갈 수없는 이웃(INF) or X보다 큰 거리는 갈 수 없음
  • 가까운 집부터 확인하기 위해 정렬
    • 거리를 누적하며 X를 넘으면 값 초기화해주며 날 세기

계속 틀리는 이유가 long형을 안써서인줄 알았는데 떡돌리는 날짜에서 잘못됐었네요...

• 처음 아이디어(떡 돌리는 최소 일 구하기)

  int left = 0;
  int right = N - 1;
  int cnt = 0;
  while (left <= right) {
      int tmp = dist[right];
      right--;
  
      while (left <= right && tmp + dist[left] <= X) {
          tmp += dist[left];
          left++;
      }
      cnt++;
  }

  • 이런식으로 가장 큰 값이랑 작은값들의 조합으로 만드려했는데 이 방법은 왜 안될까요,,,,,

[yeongleej]

🤔 시간복잡도 고려사항

• N ≤ 1,000
• M ≤ 100,000

=> 다익스트라 시간복잡도 : O(E logV)

💡 풀이 아이디어

• 다익스트라 알고리즘으로 성현이네 집으로부터 다른 집들까지의 거리 구하기
• 구한 거리의 왕복이 X로 못가면 return -1
• 거리들을 정렬해서 갈 수 있는 최소 일 수 구하기
  • 가까운 거리부터 순차적으로 가기 => 귀찮은 성현이는 하루에 X보다 먼 거리를 걷지 않고 거리가 가까운 집부터 방문한다. 는 조건 때문에
  • 맨 앞과 맨 뒤를 탐욕적으로 탐색하는 투포인터는 실패??? 인 것 같습니다. 😫

[Jewan1120]

🤔 시간복잡도 고려사항

• 2 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000
• 다익스트라 충분히 가능!

💡 풀이 아이디어

• 성현이네 집에서 모든 집들로 향하는 최단 거리를 구해야 함 → 다익스트라
• 성현이는 거리가 가까운 집부터 방문한다 → 정렬
• 정렬했을 때 가장 멀리 떨어진 집 dist[n-1]이 하루에 왕복 불가능하다면 -1 출력
• 그리디한 방식으로 하루에 최대한 많이 배달하기!