so-devlog
🌙
🧩 Problem Solving

[SWEA] 전기자동차 충전소

date
Aug 30, 2022
slug
swea-electric-car-charge
author
status
Public
category
🧩 Problem Solving
tags
SWEA
summary
type
Post
thumbnail
SWEA.jpeg

문제 분석 및 설계

2≤home≤30, map_size = 31*31, 최대 2개의 충전소 설치이므로 가능한 모든 충전소 위치에 대한 완전탐색을 해도 시간초과가 나지 않을 것이라고 판단
  • 31*31 사이즈의 맵 내에서 가능한 모든 2개의 점을 순열로 생성한 후
  • 각 경우마다 해당 충전소 위치 정보에 따라 각 집까지의 최소 거리를 계산하여 최소거리 갱신
    • 조건1) 집 위에 충전소가 지어진 경우 제외
    • 조건2) 충전소 1개만으로 충전이 가능한 경우, 이 경우를 우선으로 함
    • 조건3) 두 충전소 중 더 가까운 거리에 있는 충전소를 우선으로 함
  • 조건1 해결) 충전소까지의 거리가 0인 경우 제외
  • 조건2 해결)
      1. 최소 필요한 충전소 개수 확인(1번으로 확인 후 체크, 남아있다면 2번으로 확인 후 체크)
      1. 필요한 충전소 개수에 따라 계산 다르게
        1. 1개 필요) 1번 충전소 기준으로 모두 계산
        2. 2개 필요) 1번, 2번 충전소에 대하여 매번 더 가까운 곳으로 충전 실시
        3. 3개 필요) 제외
  • 조건3 해결) 각 충전소까지의 거리 모두 확인 후 더 가까운 거리로 할 것, 조건2 해결 시 함께 해결됨
 

실패

  • 1번 충전소가 충전 가능 거리 내부에 있으면 무조건 충전하도록 로직을 짰기 때문에 최소 거리를 보장할 수 없음(1번과 2번 모두 범위 내에 있으나 2번이 최소인 경우를 무시하게 됨)
 

성공

  • 필요한 충전소의 최소 개수 먼저 세고
  • 필요 충전소 개수에 따라 거리 계산 로직 따로 분리
  • 불필요한 state 변수 제거
 

주의할 점 및 회고

  • 더 가까운 곳으로 충전하는 것보다 충전소 개수를 최소로 하는 것이 더 우선순위에 있으므로 충전소 개수를 먼저 파악하는 것이 우선
  • 각 객체(ex. 집, 노드…)의 위치를 기억하고 거리를 계산해야 하는 경우, 객체 클래스 생성하여 ArrayList로 저장해두자!