Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- Smilegate
- 유니온파인드
- LIS #Algorithm #요소추적
- 코딩테스트
- 서버개발캠프
- 백준
- IBK기업은행 #기업은행 #디지털 #직무 #정리
- 알고리즘
- 카카오인턴
- 삼성 #코테 #2020상반기 #c++
- 코테
- 카카오
- 1편
- 소감
- Union-find
- Algorithm
- c++
- 투포인터
- 스마일게이트
- 중반부
- BaekJoon
- 식단
- BFS
- 보석쇼핑
Archives
- Today
- Total
짱아의 개발 기록장
백준 10775번. 공항(c++) / 유니온파인드 본문
반응형
아이디어가 생각나지 않아 다른 분의 아이디어를 참고하여 유니온파인드로 구현했다.
핵심 아이디어는 3번 게이트로 들어오게 되면, 3->2를 가리키도록 union해주어야 한다.
따라서, 다시 한 번 3번 게이트로 다른 비행기가 들어오면 바로 3의 Parent인 2에 넣어줄 수 있게 된다.
만약 Parent값이 게이트 범위 안에 있지 않다면, 바로 공항은 폐쇄된다.
코드 첨부
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
32
33
34
35
36
37
38
39
40
41
42
43
|
// 공항
#include <iostream>
#include <vector>
using namespace std;
int g, p, n;
vector<int> airplane;
int num = 0;
int connect[100001] = {0, }; // 유니온파인드
int find(int x){
if(connect[x] == x){
return x;
}else{
return connect[x] = find(connect[x]);
}
}
int main()
{
cin>>g>>p;
for(int i=1; i<=g; i++){
connect[i] = i;
}
for(int i=0; i<p; i++){
cin>>n;
airplane.push_back(n);
}
for(int i=0; i<airplane.size(); i++){
int a = find(airplane[i]);
if(1<=a && a<=g){
// a와 a-1을 연결해준다.
connect[a] = a-1;
num++;
}else{
break;
}
}
cout<<num<<"\n";
return 0;
}
|
cs |
문제 첨부
반응형
'Algorithm > Baekjoon' 카테고리의 다른 글
백준 1254번. 팰린드롬 만들기(c++) / 문자열 (0) | 2021.01.05 |
---|---|
백준 14002번. 가장 긴 증가하는 부분 수열 4(c++) / LIS (0) | 2020.09.23 |
백준 1854번. K번째 최단 경로(c++) / 다익스트라 (0) | 2020.08.31 |
백준 4386번. 별자리 만들기(c++) / MST(kruskal) (0) | 2020.08.30 |
백준 10815번. 숫자 카드(c++) / 이분 탐색 (0) | 2020.08.27 |
Comments