μ°μ κΈ°λ‘ πͺ
[νλ‘κ·Έλλ¨Έμ€] λλκ³Ό λ§λ κ·Έλν λ³Έλ¬Έ
[νλ‘κ·Έλλ¨Έμ€] λλκ³Ό λ§λ κ·Έλν
kite707 2025. 1. 15. 21:55https://school.programmers.co.kr/learn/courses/30/lessons/258711
νλ‘κ·Έλλ¨Έμ€
SWκ°λ°μλ₯Ό μν νκ°, κ΅μ‘, μ±μ©κΉμ§ Total Solutionμ μ 곡νλ κ°λ°μ μ±μ₯μ μν λ² μ΄μ€μΊ ν
programmers.co.kr
λ¬Έμ λΆμ
μλμ κ°μ΄ λλλͺ¨μ, λ§λλͺ¨μ, 8μλͺ¨μ κ·Έλνκ° μλ€.
μ¬κΈ°μ λ¬Έμ μ ν΅μ¬μ “μ΄ κ·Έλνλ€κ³Ό 무κ΄ν μ μ μ νλ μμ±ν λ€, κ° λλ λͺ¨μ κ·Έλν, λ§λ λͺ¨μ κ·Έλν, 8μ λͺ¨μ κ·Έλνμ μμμ μ μ νλλ‘ ν₯νλ κ°μ λ€μ μ°κ²°”νλ€λ λΆλΆμ΄λ€.
μ¦ μλμ κ°μ΄ μ μ μ μ°ΎμΌλ©΄ κ±°κΈ°μ μ°κ²°λ κ²μ λλ, λ§λ, 8μκ·Έλν μ€ νλμ¬μΌ νλ€λ μ리μ΄λ€.
κ·Έλ κΈ°μ μ μ μ μλμ κ°μ΄ λλκ·Έλν 2κ°λ₯Ό ν©μΉ κ² κ°μ λͺ¨μμ΄ λΆμ΄μκ±°λ νλ μΌμ μλ€. (λλ κ΄ν μ΄ κ²½μ°λ₯Ό μκ°νλ©΄μ μ΄λ ΅κ² μκ°νμλ€.)
μ¬κΈ°κΉμ§ μ΄ν΄νλ©΄ λ¬Έμ λ λ§μ΄ λ¨μν΄μ§λ€. λ¨Όμ μ μ μ μ°Ύκ³ , κ° λΆλΆμ μ°κ²°λ κ·Έλνλ€μ΄ μ΄λ€ λͺ¨μ(λλ, λ§λ, 8μ)μΈμ§ νλ³ν΄λ΄λ©΄ λλ€.
μμ΄λμ΄
μμ μ΄ν΄λ΄€λ―μ΄ λ¬Έμ λ ν¬κ² λ λΆλΆμΌλ‘ λλλ€.
- μ μ μ°ΎκΈ°
- κ° λΆλΆμ μ°κ²°λ κ·Έλν λͺ¨μ νλ³νκΈ°
μ μ μ°ΎκΈ°
λ¨Όμ μ μ μ 쑰건μ μλμ κ°λ€.
- λ€μ΄μ€λ κ°μ μ μκ³ , λκ°λ κ°μ λ§ μλ€.
- λ€μ΄μ€λ κ°μ μ κ°μκ° 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);
}