λ¬Έμ
μ½λ
#include <iostream>
using namespace std;
int parent[100001];
int G, P, ans;
int find(int x){
if(x == parent[x]) return x;
else return parent[x] = find(parent[x]);
}
void union_parent(int a, int b){
a = find(a);
b = find(b);
parent[a] = b;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
for(int i=0; i<=100000; i++) parent[i] = i;
cin>>G>>P;
for(int i=1; i<=G; i++){
int gate; cin>>gate;
if(find(gate) == 0) break;
else{
ans++;
union_parent(find(gate), find(gate)-1);
}
}
cout<<ans;
}
νμ΄
μ²μμ λ¬Έμ μ΄ν΄κ° μ μ κ°μ΅λλ€.
곡νμλ Pκ°μ λΉνκΈ°κ° μμλλ‘ λμ°©ν μμ μ΄λ©°, λΉμ μ iλ²μ§Έ λΉνκΈ°λ₯Ό 1λ²λΆν° gi (1 ≤ gi ≤ G) λ²μ§Έ κ²μ΄νΈ μ€ νλμ μꡬμ μΌλ‘ λνΉνλ € νλ€. λΉνκΈ°κ° μ΄λ κ²μ΄νΈμλ λνΉν μ μλ€λ©΄ 곡νμ΄ νμλκ³ , μ΄ν μ΄λ€ λΉνκΈ°λ λμ°©ν μ μλ€.
μ΄ λ§μ gκ° 3μ΄λΌλ©΄ λΉνκΈ°κ° 1, 2, 3 μ€ ν κ΅°λ° λνΉν μ μκ³ , λ§μ½ λνΉ κ°λ₯ν κ³³ μ λΆκ° μ΄λ―Έ λΉνκΈ°λ‘ κ½ μ°¨μλ€λ©΄ λ μ΄μ μ무 λΉνκΈ°λ λνΉνμ§ λͺ»νκ³ κ³΅νμ νμνλ€λ λ§μ λλ€.
νμ΄ κ°μ κ²½μ°λ λ€λ₯Έ λΈλ‘κ·Έμ νμ΄λ₯Ό λ³΄κ³ ν΄κ²°νλλ° κ΅μ₯ν λ νΉν νμ΄μμ΅λλ€.
λνΉν λ gλ²μ λ Έλμ g-1 λ Έλλ₯Ό ν©μΉλ μμ΄λμ΄μΈλ°, ν΄κ²° λ°©λ²μ gλ² κ²μ΄νΈλΆν° μ°¨λ‘λλ‘ λνΉμν€λ κ²μ λλ€. gλ²μ΄ μ°¨μμΌλ©΄ g-1, g-2, ... ,1λ²κΉμ§ λνΉν ν 1λ²λ μ°¨μμΌλ©΄ μ’ λ£ν©λλ€.
λ§μ½ gλ²μ λ Έλκ° 0μ΄ μλλΌλ©΄ λνΉν μ μλ€λ κ²μ΄νΈκ° μ μ΄λ ν κ°λ λ¨μλ€λ μλ―Έκ° λμ΄ λνΉμν€κ³ , 0μ΄λ©΄ μ’ λ£νλ νμ΄μ λλ€.
μμλ₯Ό λ€λ©΄ μλμ κ°μ΅λλ€.
4
6
2
2
3
3
4
4
μμ κ°μ μ λ ₯μμ μ € μ²μ μ΄κΈ°κ°μ μΈν νκ³ λλ©΄ parent λ°°μ΄μ λ€μκ³Ό κ°μ΅λλ€.
- parent[1] = 1, parent[2] = 2, parent[3] = 3, parent[4] = 4, parent[5] = 5, parent[6] = 6
μ΄μ g μ λ ₯ μμλλ‘ μ΄ν΄λ³΄λ©΄ μ €μ²μ gκ° 2μΌ κ²½μ° union_parent(2, 1)μ μνν©λλ€. μννκ² λλ©΄ parent[2] = 1μ΄ λ©λλ€.
- parent[1] = 1, parent[2] = 1, parent[3] = 3, parent[4] = 4, parent[5] = 5, parent[6] = 6
λ€μ μ λ ₯λ gκ° 2κ° λ€μ΄μ€κ² λ©λλ€. union_parent(1, 0)μ μνν©λλ€. μννκ²λλ©΄ parent[1] = 0μ΄ λ©λλ€.
- parent[1] = 0, parent[2] = 1, parent[3] = 3, parent[4] = 4, parent[5] = 5, parent[6] = 6
λ€μμ gκ° 3μ΄ λ€μ΄μ€κ² λ©λλ€. union_parent(3, 2)μ μνν©λλ€. μννκ²λλ©΄ parent[3] = 2κ° λ©λλ€.
- parent[1] = 0, parent[2] = 1, parent[3] = 2, parent[4] = 4, parent[5] = 5, parent[6] = 6
λ€μλ gκ° 3μ΄ λ€μ΄μ€κ² λ©λλ€. find(3) = 0μ΄ λ©λλ€. λ°λΌμ μ’ λ£ν©λλ€.
'Algorithm π§π»βπ» > λ°±μ€(BOJ)' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[λ°±μ€,c++] 17136λ² - μμ’ μ΄ λΆμ΄κΈ° (0) | 2022.09.06 |
---|---|
[λ°±μ€,c++] 2533λ² - μ¬νλ§ μλΉμ€(SNS) (0) | 2022.09.04 |
[λ°±μ€,c++] 15681λ² - νΈλ¦¬μ 쿼리 (0) | 2022.09.04 |
[λ°±μ€,c++] 4195λ² - μΉκ΅¬ λ€νΈμν¬ (0) | 2022.09.02 |
[λ°±μ€,c++] 18116λ² - λ‘λ΄ μ‘°λ¦½ (0) | 2022.09.02 |
[λ°±μ€,c++] 17144λ² - λ―ΈμΈλ¨Όμ§ μλ ! (0) | 2022.09.02 |
λκΈ