Β«   2025/03   Β»
일 μ›” ν™” 수 λͺ© 금 ν† 
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31
Archives
Recent Posts
03-06 14:24

Today
Total

Recent Comments
관리 메뉴

μ—°μ˜ 기둝 πŸͺ

[ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€] 도넛과 λ§‰λŒ€ κ·Έλž˜ν”„ λ³Έλ¬Έ

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

[ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€] 도넛과 λ§‰λŒ€ κ·Έλž˜ν”„

kite707 2025. 1. 15. 21:55

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

 

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

SW개발자λ₯Ό μœ„ν•œ 평가, ꡐ윑, μ±„μš©κΉŒμ§€ Total Solution을 μ œκ³΅ν•˜λŠ” 개발자 μ„±μž₯을 μœ„ν•œ λ² μ΄μŠ€μΊ ν”„

programmers.co.kr

 

문제 뢄석

μ•„λž˜μ™€ 같이 도넛λͺ¨μ–‘, λ§‰λŒ€λͺ¨μ–‘, 8자λͺ¨μ–‘ κ·Έλž˜ν”„κ°€ μžˆλ‹€.

μ—¬κΈ°μ„œ 문제의 핡심은 이 κ·Έλž˜ν”„λ“€κ³Ό λ¬΄κ΄€ν•œ 정점을 ν•˜λ‚˜ μƒμ„±ν•œ λ’€, 각 도넛 λͺ¨μ–‘ κ·Έλž˜ν”„, λ§‰λŒ€ λͺ¨μ–‘ κ·Έλž˜ν”„, 8자 λͺ¨μ–‘ κ·Έλž˜ν”„μ˜ μž„μ˜μ˜ 정점 ν•˜λ‚˜λ‘œ ν–₯ν•˜λŠ” 간선듀을 μ—°κ²°ν–ˆλ‹€λŠ” 뢀뢄이닀.

즉 μ•„λž˜μ™€ 같이 정점을 찾으면 거기에 μ—°κ²°λœ 것은 도넛, λ§‰λŒ€, 8μžκ·Έλž˜ν”„ 쀑 ν•˜λ‚˜μ—¬μ•Ό ν•œλ‹€λŠ” μ†Œλ¦¬μ΄λ‹€.

그렇기에 정점에 μ•„λž˜μ™€ 같이 λ„λ„›κ·Έλž˜ν”„ 2개λ₯Ό ν•©μΉœ 것 같은 λͺ¨μ–‘이 λΆ™μ–΄μžˆκ±°λ‚˜ ν•˜λŠ” 일은 μ—†λ‹€. (λ‚˜λŠ” 괜히 이 경우λ₯Ό μƒκ°ν•˜λ©΄μ„œ μ–΄λ ΅κ²Œ μƒκ°ν–ˆμ—ˆλ‹€.)

μ—¬κΈ°κΉŒμ§€ μ΄ν•΄ν•˜λ©΄ λ¬Έμ œλŠ” 많이 λ‹¨μˆœν•΄μ§„λ‹€. λ¨Όμ € 정점을 μ°Ύκ³ , 각 뢀뢄에 μ—°κ²°λœ κ·Έλž˜ν”„λ“€μ΄ μ–΄λ–€ λͺ¨μ–‘(도넛, λ§‰λŒ€, 8자)인지 νŒλ³„ν•΄λ‚΄λ©΄ λœλ‹€.

아이디어

μ•žμ„œ μ‚΄νŽ΄λ΄€λ“―μ΄ λ¬Έμ œλŠ” 크게 두 λΆ€λΆ„μœΌλ‘œ λ‚˜λ‰œλ‹€.

  1. 정점 μ°ΎκΈ°
  2. 각 뢀뢄에 μ—°κ²°λœ κ·Έλž˜ν”„ λͺ¨μ–‘ νŒλ³„ν•˜κΈ°

정점 μ°ΎκΈ°

λ¨Όμ € μ •μ μ˜ 쑰건은 μ•„λž˜μ™€ κ°™λ‹€.

  1. λ“€μ–΄μ˜€λŠ” 간선은 μ—†κ³ , λ‚˜κ°€λŠ” κ°„μ„ λ§Œ μžˆλ‹€.
  2. λ“€μ–΄μ˜€λŠ” κ°„μ„ μ˜ κ°œμˆ˜κ°€ 0인것이 μ—¬λŸ¬κ°œλΌλ©΄ 그쀑 λ‚˜κ°€λŠ” κ°„μ„ μ˜ μˆ˜κ°€ κ°€μž₯ 큰 것이 정점이닀.

1번 쑰건은 “이 κ·Έλž˜ν”„λ“€κ³Ό λ¬΄κ΄€ν•œ 정점을 ν•˜λ‚˜ μƒμ„±ν•œ λ’€, 각 도넛 λͺ¨μ–‘ κ·Έλž˜ν”„, λ§‰λŒ€ λͺ¨μ–‘ κ·Έλž˜ν”„, 8자 λͺ¨μ–‘ κ·Έλž˜ν”„μ˜ μž„μ˜μ˜ 정점 ν•˜λ‚˜λ‘œ ν–₯ν•˜λŠ” 간선듀을 μ—°κ²°ν–ˆμŠ΅λ‹ˆλ‹€.” λΌλŠ” κ΅¬μ ˆμ—μ„œ μœ μΆ”ν•  수 μžˆλ‹€. λ§Œμ•½ μ •μ μœΌλ‘œ λ“€μ–΄μ˜€λŠ” 간선이 μžˆλ‹€λ©΄ λ¬Έμ œμ—μ„œ 주어진 쑰건에 λ§žμ§€ μ•Šλ‹€.

λ§Œμ•½ μ•„λž˜μ™€ 같이 κ·Έλž˜ν”„κ°€ 생겼닀고 κ°€μ •ν•΄λ³΄μž.(1번 μ˜ˆμ‹œμ— 7번이 μΆ”κ°€λœ λͺ¨μŠ΅)

μ›λž˜ 이 κ·Έλž˜ν”„μ˜ 정점은 2번인데, λ¬Έμ œμ—μ„œ 도넛, λ§‰λŒ€, 8자 λͺ¨μ–‘ κ·Έλž˜ν”„μ˜ μž„μ˜μ˜ 정점 ν•˜λ‚˜λ‘œ ν–₯ν•˜λŠ” 간선을 μ—°κ²°ν–ˆλ‹€λŠ” 말과 λ§žμ§€ μ•ŠλŠ” 것을 확인할 수 μžˆλ‹€. κ·Έλž˜μ„œ 정점은 λ“€μ–΄μ˜€λŠ” 간선이 μ—†μ–΄μ•Ό ν•œλ‹€.

2번 쑰건을 μ΄ν•΄ν•˜κΈ° μœ„ν•΄ 1번 μ˜ˆμ‹œλ₯Ό λ‹€μ‹œ 보도둝 ν•˜μž. μš°λ¦¬λŠ” 2번 정점과 4번 정점 λͺ¨λ‘ λ“€μ–΄μ˜€λŠ” 간선이 0κ°œμ΄μ§€λ§Œ μ§κ΄€μ μœΌλ‘œ 2번 정점이 μš°λ¦¬κ°€ μ°ΎλŠ” μ •μ μž„μ„ μ•Œ 수 μžˆλ‹€. 이것도 같은 κ΅¬μ ˆμ„ 톡해 μ•Œ 수 μžˆλ‹€. 문제λ₯Ό 보면 “κ·Έλž˜ν”„λ“€κ³Ό λ¬΄κ΄€ν•œ 정점을 ν•˜λ‚˜ μƒμ„±ν•œ λ’€, 각 도넛 λͺ¨μ–‘ κ·Έλž˜ν”„, λ§‰λŒ€ λͺ¨μ–‘ κ·Έλž˜ν”„, 8자 λͺ¨μ–‘ κ·Έλž˜ν”„μ˜ μž„μ˜μ˜ 정점 ν•˜λ‚˜λ‘œ ν–₯ν•˜λŠ” 간선듀을 μ—°κ²°ν–ˆμŠ΅λ‹ˆλ‹€.”라고 ν–ˆλ‹€.

즉 μš°λ¦¬κ°€ μ°ΎλŠ” 정점은 λͺ¨λ“  κ·Έλž˜ν”„λ“€κ³Ό μ—°κ²°λ˜μ–΄ 있기 λ•Œλ¬Έμ— λ‚˜κ°€λŠ” μ •μ μ˜ κ°œμˆ˜κ°€ κ°€μž₯ λ§Žμ€ 정점이닀.

각 뢀뢄에 μ—°κ²°λœ κ·Έλž˜ν”„ λͺ¨μ–‘ νŒλ³„ν•˜κΈ°

각 κ·Έλž˜ν”„μ˜ λͺ¨μ–‘을 κ΄€μ°°ν•˜λ©΄ κ·Έλž˜ν”„μ˜ λͺ¨μ–‘을 μ–΄λ–»κ²Œ νŒλ³„ν• μ§€ μ•Œ 수 μžˆλ‹€.

λ¨Όμ € λ§‰λŒ€λͺ¨μ–‘ κ·Έλž˜ν”„λŠ” μ­‰ 따라가닀보면 λ‚˜κ°€λŠ” 간선이 μ—†λŠ” 정점이 λ‚˜μ˜€λŠ” κ·Έλž˜ν”„μ΄λ‹€. λ¬Έμ œλŠ” λ„λ„›μ΄λž‘ 8자 λͺ¨μ–‘을 μ–΄λ–»κ²Œ κ΅¬λ³„ν•˜λŠλƒμ΄λ‹€. λ‘˜ λ‹€ μ­‰ 따라가닀보면 자기 μžμ‹ μ΄ λ‚˜μ˜€κΈ° λ•Œλ¬Έμ΄λ‹€.

ν•˜μ§€λ§Œ 8자 λͺ¨μ–‘ κ·Έλž˜ν”„μ—λŠ” 도넛 λͺ¨μ–‘ κ·Έλž˜ν”„μ™€ 달리 λ‚˜κ°€λŠ” 간선이 2개인 정점이 μžˆλ‹€. 이것을 μ΄μš©ν•΄ 도넛과 8자 κ·Έλž˜ν”„λ₯Ό ꡬ뢄할 수 μžˆλ‹€.

πŸ”‘κ·Έλž˜ν”„ ꡬ뢄

λ§‰λŒ€ λͺ¨μ–‘ κ·Έλž˜ν”„ : μˆœνšŒν•˜λ‹€ 보면 λ‚˜κ°€λŠ” 간선이 1개인 정점을 λ§Œλ‚œλ‹€.
8자 λͺ¨μ–‘ κ·Έλž˜ν”„ : μˆœνšŒν•˜λ‹€ 보면 λ‚˜κ°€λŠ” 간선이 2개인 정점을 λ§Œλ‚œλ‹€.
도넛 λͺ¨μ–‘ κ·Έλž˜ν”„ : μˆœνšŒν•˜λ‹€ 보면 자기 μžμ‹ μ„ λ§Œλ‚˜κ²Œ λœλ‹€.

κ·Έλž˜μ„œ μ½”λ“œμ—λŠ” λ‚˜κ°€λŠ” 간선이 1개, 2개인 정점을 λ§Œλ‚˜λ©΄ 순회λ₯Ό λ©ˆμΆ”κ³ , λ§Œμ•½ 순회λ₯Ό λκΉŒμ§€ ν•˜κ²Œ λ˜μ–΄ λ°©λ¬Έν•œ 적이 μžˆλŠ” 정점을 λ§Œλ‚˜κ²Œ λœλ‹€λ©΄ 도넛 λͺ¨μ–‘ κ·Έλž˜ν”„λ‘œ νŒλ‹¨ν•  것이닀.

μ½”λ“œ

전체 μ½”λ“œλŠ” μ•„λž˜μ™€ κ°™λ‹€.

#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <queue>
using namespace std;

bool isExist[1000005];
int indegrees[1000005];
int outdegrees[1000005];
vector<int> vec[1000005];

bool visited[1000005];

int doughnut,stick,eight;

void bfs(int start){
    queue<int> q;
    visited[start]=true;
    
    q.push(start);
    bool flag=true;
    while(!q.empty()&&flag){
        int curVertex=q.front();
        q.pop();
        
        //λ‚˜κ°€λŠ” 간선이 0개인 정점 : λ§‰λŒ€ λͺ¨μ–‘ κ·Έλž˜ν”„
        if(outdegrees[curVertex]==0){
            stick++;
            return;
        }
        
        //λ‚˜κ°€λŠ” 간선이 2개인 정점 : 8자 λͺ¨μ–‘ κ·Έλž˜ν”„
        if(outdegrees[curVertex]==2){
            eight++;
            return;
        }
        
        for(int i=0;i<vec[curVertex].size();i++){
            int nxtVertex=vec[curVertex][i];
            //이미 λ°©λ¬Έν•œ 적이 μžˆλŠ” 정점 : 도넛 λͺ¨μ–‘ κ·Έλž˜ν”„
            if(visited[nxtVertex]){
                flag=false;
                break;
            }
            visited[nxtVertex]=true;
            q.push(nxtVertex);
        }
    }
    doughnut++;
    return;
}

vector<int> solution(vector<vector<int>> edges) {
    vector<int> answer;
    for(auto k:edges){
        isExist[k[0]]=true;
        isExist[k[1]]=true;
        
        outdegrees[k[0]]++;
        indegrees[k[1]]++;
        vec[k[0]].push_back(k[1]);
    }
    
    //정점 μ°ΎκΈ°(λ“€μ–΄μ˜€λŠ” 간선이 μ—†κ³  λ‚˜κ°€λŠ” 간선이 λ§Žμ€)
    priority_queue <pair<int,int>> cand;
    for(int i=1;i<1000005;i++){
        if(!isExist[i])continue;
        if(indegrees[i]==0)cand.push({outdegrees[i],i}); // λ‚˜κ°€λŠ” κ°„μ„  개수, μ •μ λ²ˆν˜Έ
    }
    
    //λ“€μ–΄μ˜€λŠ” 간선이 μ—†λŠ” 정점듀을 λ‚˜κ°€λŠ” κ°„μ„  개수둜 μ •λ ¬ν•œ λ’€ κ°€μž₯ μœ„μ˜ 정점을 κ°€μ Έμ˜΄ : 메인 정점
    int mainVertex = cand.top().second;
    
    //메인 정점에 μ—°κ²°λœ 정점듀을 ν•˜λ‚˜μ”© μž‘μ•„ bfsλ₯Ό ν†΅ν•œ 순회
    for(int i=0;i<vec[mainVertex].size();i++){
        int tmpVertex=vec[mainVertex][i];
        bfs(tmpVertex);
    }
    
    answer.push_back(mainVertex);
    answer.push_back(doughnut);
    answer.push_back(stick);
    answer.push_back(eight);
    
    return answer;
}

 

μ‹€μˆ˜ν–ˆλ˜ λΆ€λΆ„

λ‚˜λŠ” λ§ˆμ§€λ§‰ ν…ŒμŠ€νŠΈμΌ€μ΄μŠ€μΈ 35번 ν…ŒμŠ€νŠΈμΌ€μ΄μŠ€λ§Œ 톡과λ₯Ό λͺ»ν–ˆμ—ˆλŠ”데 κ·Έ μ΄μœ λŠ” μ²˜μŒμ— 정점 μ°ΎκΈ° 뢀뢄을 μ•„λž˜μ™€ 같이 μ§°κΈ° λ•Œλ¬Έμ΄λ‹€.

    //정점 μ°ΎκΈ°(λ“€μ–΄μ˜€λŠ” 간선이 μ—†κ³  λ‚˜κ°€λŠ” 간선이 λ§Žμ€)
    priority_queue <pair<int,int>> cand;
    for(int i=1;i<1000005;i++){
        if(!isExist[i])break; //μ‹€μˆ˜ν•œ λΆ€λΆ„, 이후 continue둜 λ°”κΎΈμ–΄ 성곡
        if(indegrees[i]==0)cand.push({outdegrees[i],i}); // λ‚˜κ°€λŠ” κ°„μ„  개수, μ •μ λ²ˆν˜Έ
    }

λ‚΄ λ§ˆμŒλŒ€λ‘œ μ •μ μ˜ λ²ˆν˜Έκ°€ μˆœμ„œλŒ€λ‘œ λΆ€μ—¬λœλ‹€κ³  μƒκ°ν–ˆλŠ”λ° 문제의 μ œν•œ 사항을 보면 그런 말은 μ—†λ‹€. 즉 1 3 5 7번 정점이 μ‘΄μž¬ν•  수 μžˆλ‹€λŠ” 말이닀. 그런데 μœ„μ™€ 같이 break문을 κ±Έλ©΄ 1번 μ •μ λ§Œ κ°„μ„ μ˜ 개수λ₯Ό μ²΄ν¬ν•˜κΈ° λ•Œλ¬Έμ— segmentation fault (core dumped)κ°€ λ°œμƒν•œλ‹€.

또 μ²˜μŒμ— 짰을 λ•ŒλŠ” μ•„λž˜ bfsλ₯Ό μˆœνšŒν•  λ•Œ μƒˆλ‘œμš΄ μ •μ μ—μ„œ 순회λ₯Ό μ‹œμž‘ν•  λ•Œ λ§ˆλ‹€ visited배열을 μ΄ˆκΈ°ν™” ν–ˆμ—ˆλ‹€. 그런데 μƒκ°ν•΄λ³΄λ‹ˆ 각 정점은 ν•˜λ‚˜μ˜ κ·Έλž˜ν”„λ“€κ³Ό μ—°κ²°λœλ‹€. 그렇기에 κ·Έλž˜ν”„κ°„μ— 정점을 κ³΅μœ ν•˜μ§€ μ•Šμ•„ visited배열을 계속 μ΄ˆκΈ°ν™”ν•  ν•„μš”κ°€ μ—†λ‹€.

    //메인 정점에 μ—°κ²°λœ 정점듀을 ν•˜λ‚˜μ”© μž‘μ•„ bfsλ₯Ό ν†΅ν•œ 순회
    for(int i=0;i<vec[mainVertex].size();i++){
		    fill(&visited[0],&visited[0]+1000005,false); //μ •λ‹΅ μ½”λ“œμ—μ„  빠진 λΆ€λΆ„
        int tmpVertex=vec[mainVertex][i];
        bfs(tmpVertex);
    }