[ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]level.2 - 배달(C++)

2023. 7. 10. 13:14Β·πŸ–₯️ Study Note/Coding Test

https://school.programmers.co.kr/learn/courses/30/lessons/12978

 

ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€

μ½”λ“œ μ€‘μ‹¬μ˜ 개발자 μ±„μš©. μŠ€νƒ 기반의 ν¬μ§€μ…˜ λ§€μΉ­. ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€μ˜ 개발자 λ§žμΆ€ν˜• ν”„λ‘œν•„μ„ λ“±λ‘ν•˜κ³ , λ‚˜μ™€ 기술 ꢁ합이 잘 λ§žλŠ” 기업듀을 λ§€μΉ­ λ°›μœΌμ„Έμš”.

programmers.co.kr

문제 μ„€λͺ…

N개의 λ§ˆμ„λ‘œ 이루어진 λ‚˜λΌκ°€ μžˆμŠ΅λ‹ˆλ‹€. 이 λ‚˜λΌμ˜ 각 λ§ˆμ„μ—λŠ” 1λΆ€ν„° NκΉŒμ§€μ˜ λ²ˆν˜Έκ°€ 각각 ν•˜λ‚˜μ”© λΆ€μ—¬λ˜μ–΄ μžˆμŠ΅λ‹ˆλ‹€. 각 λ§ˆμ„μ€ μ–‘λ°©ν–₯으둜 톡행할 수 μžˆλŠ” λ„λ‘œλ‘œ μ—°κ²°λ˜μ–΄ μžˆλŠ”λ°, μ„œλ‘œ λ‹€λ₯Έ λ§ˆμ„ 간에 이동할 λ•ŒλŠ” 이 λ„λ‘œλ₯Ό μ§€λ‚˜μ•Ό ν•©λ‹ˆλ‹€. λ„λ‘œλ₯Ό μ§€λ‚  λ•Œ κ±Έλ¦¬λŠ” μ‹œκ°„μ€ λ„λ‘œλ³„λ‘œ λ‹€λ¦…λ‹ˆλ‹€. ν˜„μž¬ 1번 λ§ˆμ„μ— μžˆλŠ” μŒμ‹μ μ—μ„œ 각 λ§ˆμ„λ‘œ μŒμ‹ 배달을 ν•˜λ €κ³  ν•©λ‹ˆλ‹€. 각 λ§ˆμ„λ‘œλΆ€ν„° μŒμ‹ 주문을 λ°›μœΌλ €κ³  ν•˜λŠ”λ°, N개의 λ§ˆμ„ μ€‘μ—μ„œ K μ‹œκ°„ μ΄ν•˜λ‘œ 배달이 κ°€λŠ₯ν•œ λ§ˆμ„μ—μ„œλ§Œ 주문을 λ°›μœΌλ €κ³  ν•©λ‹ˆλ‹€. λ‹€μŒμ€ N = 5, K = 3인 경우의 μ˜ˆμ‹œμž…λ‹ˆλ‹€.

μœ„ κ·Έλ¦Όμ—μ„œ 1번 λ§ˆμ„μ— μžˆλŠ” μŒμ‹μ μ€ [1, 2, 4, 5] 번 λ§ˆμ„κΉŒμ§€λŠ” 3 μ΄ν•˜μ˜ μ‹œκ°„μ— 배달할 수 μžˆμŠ΅λ‹ˆλ‹€. κ·ΈλŸ¬λ‚˜ 3번 λ§ˆμ„κΉŒμ§€λŠ” 3μ‹œκ°„ μ΄λ‚΄λ‘œ 배달할 수 μžˆλŠ” κ²½λ‘œκ°€ μ—†μœΌλ―€λ‘œ 3번 λ§ˆμ„μ—μ„œλŠ” 주문을 λ°›μ§€ μ•ŠμŠ΅λ‹ˆλ‹€. λ”°λΌμ„œ 1번 λ§ˆμ„μ— μžˆλŠ” μŒμ‹μ μ΄ 배달 주문을 받을 수 μžˆλŠ” λ§ˆμ„μ€ 4κ°œκ°€ λ©λ‹ˆλ‹€.

λ§ˆμ„μ˜ 개수 N, 각 λ§ˆμ„μ„ μ—°κ²°ν•˜λŠ” λ„λ‘œμ˜ 정보 road, μŒμ‹ 배달이 κ°€λŠ₯ν•œ μ‹œκ°„ Kκ°€ λ§€κ°œλ³€μˆ˜λ‘œ μ£Όμ–΄μ§ˆ λ•Œ, μŒμ‹ 주문을 받을 수 μžˆλŠ” λ§ˆμ„μ˜ 개수λ₯Ό return ν•˜λ„λ‘ solution ν•¨μˆ˜λ₯Ό μ™„μ„±ν•΄μ£Όμ„Έμš”.

μ œν•œμ‚¬ν•­

  • λ§ˆμ„μ˜ 개수 N은 1 이상 50 μ΄ν•˜μ˜ μžμ—°μˆ˜μž…λ‹ˆλ‹€.
  • road의 길이(λ„λ‘œ μ •λ³΄μ˜ 개수)λŠ” 1 이상 2,000 μ΄ν•˜μž…λ‹ˆλ‹€.
  • road의 각 μ›μ†ŒλŠ” λ§ˆμ„μ„ μ—°κ²°ν•˜κ³  μžˆλŠ” 각 λ„λ‘œμ˜ 정보λ₯Ό λ‚˜νƒ€λƒ…λ‹ˆλ‹€.
  • roadλŠ” 길이가 3인 배열이며, μˆœμ„œλŒ€λ‘œ (a, b, c)λ₯Ό λ‚˜νƒ€λƒ…λ‹ˆλ‹€.
    • a, b(1 ≤ a, b ≤ N, a != b)λŠ” λ„λ‘œκ°€ μ—°κ²°ν•˜λŠ” 두 λ§ˆμ„μ˜ 번호이며, c(1 ≤ c ≤ 10,000, cλŠ” μžμ—°μˆ˜)λŠ” λ„λ‘œλ₯Ό μ§€λ‚˜λŠ”λ° κ±Έλ¦¬λŠ” μ‹œκ°„μž…λ‹ˆλ‹€.
    • 두 λ§ˆμ„ a, bλ₯Ό μ—°κ²°ν•˜λŠ” λ„λ‘œλŠ” μ—¬λŸ¬ κ°œκ°€ μžˆμ„ 수 μžˆμŠ΅λ‹ˆλ‹€.
    • ν•œ λ„λ‘œμ˜ 정보가 μ—¬λŸ¬ 번 μ€‘λ³΅ν•΄μ„œ μ£Όμ–΄μ§€μ§€ μ•ŠμŠ΅λ‹ˆλ‹€.
  • KλŠ” μŒμ‹ 배달이 κ°€λŠ₯ν•œ μ‹œκ°„μ„ λ‚˜νƒ€λ‚΄λ©°, 1 이상 500,000 μ΄ν•˜μž…λ‹ˆλ‹€.
  • μž„μ˜μ˜ 두 λ§ˆμ„κ°„μ— 항상 이동 κ°€λŠ₯ν•œ κ²½λ‘œκ°€ μ‘΄μž¬ν•©λ‹ˆλ‹€.
  • 1번 λ§ˆμ„μ— μžˆλŠ” μŒμ‹μ μ΄ K μ΄ν•˜μ˜ μ‹œκ°„μ— 배달이 κ°€λŠ₯ν•œ λ§ˆμ„μ˜ 개수λ₯Ό return ν•˜λ©΄ λ©λ‹ˆλ‹€.

λ‚΄ μ½”λ“œ

κ°€μ€‘μΉ˜κ°€ μžˆλŠ” λ…Έλ“œ κ°„ μ΅œλ‹¨ 거리λ₯Ό κ΅¬ν•˜λŠ” μ•Œκ³ λ¦¬μ¦˜μΈ 'λ‹€μ΅μŠ€νŠΈλΌ μ•Œκ³ λ¦¬μ¦˜' 을 μ‚¬μš©ν•˜μ—¬ ν’€μ—ˆλ‹€. 아직 이 μœ ν˜•μ— μ΅μˆ™ν•΄μ§€μ§€ μ•Šμ€ 것 κ°™μ•„ μ’€ λͺ¨μ•„μ„œ 풀어봐야겠닀.

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

// 거리기쀀 μ˜€λ¦„μ°¨μˆœ μ •λ ¬
struct comp {
    bool operator()(pair<int, int> p1, pair<int, int>p2)
    {
        if (p1.second <= p2.second)
            return true;
        return false;
    }
};

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    int max_int = numeric_limits<int>::max();
    vector<vector<int>> country_map(N, vector<int>(N, max_int));
    vector<int> distance(N, max_int);
    priority_queue<pair<int, int>, vector<pair<int, int>>, comp> q;

    for (auto r : road)
    {
        int n1 = r[0] - 1;
        int n2 = r[1] - 1;
        int d = r[2];
        
        country_map[n1][n2] = country_map[n1][n2] < d ? country_map[n1][n2] : d;
        country_map[n2][n1] = country_map[n2][n1] < d ? country_map[n2][n1] : d;
    }

    // 0λΆ€ν„° iκΉŒμ§€ κ°€λŠ” μ΅œλ‹¨ 거리 μ°ΎκΈ°(λ‹€μ΅μŠ€νŠΈλΌ)
    distance[0] = 0;
    q.emplace(make_pair(0, 0));
    while (!q.empty())
    {
        auto top = q.top();
        q.pop();

        int n = top.first;
        int d = top.second;

        for (int i = 0; i < country_map[n].size(); ++i)
        {
            if(country_map[n][i] >= max_int)
                continue;
            
            int village_node = i;
            int village_distance = country_map[n][i] + d;

            if (village_distance <= distance[village_node])
            {
                distance[village_node] = village_distance;
                q.emplace(make_pair(village_node, village_distance));
            }
        }

    }

    // K이내인 λ…Έλ“œ μ°ΎκΈ°
    for (int i = 0; i < distance.size(); ++i)
    {
        if (distance[i] <= K)
            ++answer;
    }

    return answer;
}

μ €μž‘μžν‘œμ‹œ λΉ„μ˜λ¦¬ λ³€κ²½κΈˆμ§€ (μƒˆμ°½μ—΄λ¦Ό)

'πŸ–₯️ Study Note > Coding Test' μΉ΄ν…Œκ³ λ¦¬μ˜ λ‹€λ₯Έ κΈ€

[ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]level.2 - κ΄„ν˜Έ νšŒμ „ν•˜κΈ°(C++)  (0) 2023.07.12
[ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]level.2 - λ§ˆλ²•μ˜ μ—˜λ¦¬λ² μ΄ν„°(C++)  (0) 2023.07.11
[ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]level.2 - 두 큐 ν•© κ°™κ²Œ λ§Œλ“€κΈ°(C++)  (0) 2023.07.04
[ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]level.2 - N개의 μ΅œμ†Œκ³΅λ°°μˆ˜(C++)  (0) 2023.07.03
[ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]level.2 - 점프와 μˆœκ°„ 이동(C++)  (0) 2023.06.30
'πŸ–₯️ Study Note/Coding Test' μΉ΄ν…Œκ³ λ¦¬μ˜ λ‹€λ₯Έ κΈ€
  • [ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]level.2 - κ΄„ν˜Έ νšŒμ „ν•˜κΈ°(C++)
  • [ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]level.2 - λ§ˆλ²•μ˜ μ—˜λ¦¬λ² μ΄ν„°(C++)
  • [ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]level.2 - 두 큐 ν•© κ°™κ²Œ λ§Œλ“€κΈ°(C++)
  • [ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]level.2 - N개의 μ΅œμ†Œκ³΅λ°°μˆ˜(C++)
Beankong_
Beankong_
μ£Όλ‹ˆμ–΄ ν΄λΌμ΄μ–ΈνŠΈ ν”„λ‘œκ·Έλž˜λ¨Έ 곡뢀 기둝
  • Beankong_
    Beankong's Devlog
    Beankong_
  • 전체
    였늘
    μ–΄μ œ
    • 전체 κΈ€ (146)
      • β›… Daily (0)
      • πŸ–₯️ Study Note (2)
        • C++ (1)
        • Unreal Engine (5)
        • Coding Test (123)
        • Design Patteren (5)
        • VCS (Git..) (1)
        • Server (1)
      • 🧭 Devlog (8)
        • μ˜€λ‹΅λ…ΈνŠΈ (4)
        • UE5 GameLift Server Test Project (1)
        • TIL (3)
  • hELLOΒ· Designed Byμ •μƒμš°.v4.10.3
Beankong_
[ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]level.2 - 배달(C++)
μƒλ‹¨μœΌλ‘œ

ν‹°μŠ€ν† λ¦¬νˆ΄λ°”