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
- 유니온파인드
- 스마일게이트
- 1편
- 투포인터
- Smilegate
- IBK기업은행 #기업은행 #디지털 #직무 #정리
- 백준
- 중반부
- Algorithm
- 코딩테스트
- 카카오인턴
- BFS
- 알고리즘
- LIS #Algorithm #요소추적
- 소감
- Union-find
- 삼성 #코테 #2020상반기 #c++
- c++
- 코테
- 식단
- 서버개발캠프
- 카카오
- 보석쇼핑
- BaekJoon
Archives
- Today
- Total
짱아의 개발 기록장
[Algorithm] 2020 상반기 삼성전자 코딩테스트 오후 - 스타트 택시(c++) 본문
Algorithm/삼성 sw 역량테스트 기출
[Algorithm] 2020 상반기 삼성전자 코딩테스트 오후 - 스타트 택시(c++)
jungahshin 2020. 7. 20. 22:26반응형
이 문제는 한 번에 맞을 수 있었다.
최단 거리의 사람을 판별하는 것이 핵심 포인트!
나는 벡터에 <거리, customer idx>를 넣어주었고 sort해주어서 가장 앞에 있는 원소들 중 거리가 똑같다면
또 다른 벡터에 <행, 열> 값을 넣고 sort해주어 0번째 있는 customer를 최단 거리에 있는 사람으로 판별했다.
주저리 설명을 너무 못한다....
코드에 주석을 달아 놓았으니 참고하시길...
코드 첨부
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
// 스타트 택시
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
int n, m, start_x, start_y, s_x, s_y, e_x, e_y;
int road[22][22] = {0, }; // 도로의 상태
long long oil = 0; // 연료
vector<pair<pair<int, int>, pair<int, int> > > customer;
map<int, int> check;// 이미 데려다 준 고객들을 map으로 표시해준다.
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
bool check_final = true; // // 연료가 부족하거나 도착지점에 도착할 수 없음을 판별
// 태울 사람의 출발지에서 목적지까지의 거리
long long bfs2(int idx)
{
//중간에 연료가 부족하거나 도착 지점에 도착할 수 없으면 -1 반환한다.
int final = 0; // 출발지에서 도착지까지의 거리
bool temp = false; // 연료가 부족하거나 도착지점에 도착할 수 없음을 판별
queue<pair<pair<int, int>, int>> q;
q.push(make_pair(make_pair(customer[idx].first.first, customer[idx].first.second), 0));
int visited[22][22] = {0, };
while(!q.empty()){
int x = q.front().first.first;
int y = q.front().first.second;
int num = q.front().second;
visited[x][y] = 1;
q.pop();
if(num>oil){
break;
}
if(x==customer[idx].second.first && y==customer[idx].second.second){
final = num;
temp = true;
break;
}
for(int i=0; i<4; i++){
int nx = x+dx[i];
int ny = y+dy[i];
if(1<=nx && nx<=n && 1<=ny && ny<=n && !visited[nx][ny]){
visited[nx][ny] = 1;
if(road[nx][ny]==0){
q.push(make_pair(make_pair(nx, ny), num+1));
}
}
}
}
if(temp == false){ // 도착지점에 도착하지 못하거나 연료가 부족한 경우
return -1;
}
return final;
}
// 태울 사람 선정
void bfs()
{
// 일단, 각 사람들까지의 최단 거리를 각각 구해보고 가장 최단 거리인 사람을 찾는다.
vector<pair<int, int> > v; // 가장 최단 거리를 구하기 위해(거리, idx k값)
for(int k=0; k<customer.size(); k++){
if(check.count(k)==0){ // 나중에 최단 거리인 고객을 check[k] = 1로 표시해준다.
queue<pair<pair<int, int>, int> > q;
q.push(make_pair(make_pair(start_x, start_y), 0));
int visited[22][22] = {0, };
while(!q.empty()){
int x = q.front().first.first;
int y = q.front().first.second;
int num = q.front().second;
visited[x][y] = 1;
q.pop();
if(x==customer[k].first.first && y==customer[k].first.second){
v.push_back(make_pair(num, k));
break;
}
for(int i=0; i<4; i++){
int nx = x+dx[i];
int ny = y+dy[i];
if(1<=nx && nx<=n && 1<=ny && ny<=n && !visited[nx][ny]){
visited[nx][ny] = 1;
if(road[nx][ny]==0){
q.push(make_pair(make_pair(nx, ny), num+1));
}
}
}
}
}
}
if(v.size()!=m){
check_final = false;
return;
}
sort(v.begin(), v.end());
vector<pair<pair<int, int>, int> > v_temp;
for(int i=0; i<v.size(); i++){
if(v[0].first == v[i].first){ // 거리가 최단으로 같아면 행과 열을 확인한다.
int idx = v[i].second;
v_temp.push_back(make_pair(make_pair(customer[idx].first.first, customer[idx].first.second), idx));
}
}
sort(v_temp.begin(), v_temp.end());
//최단 거리 -> v[0].first // customer -> v_temp[0].second
int short_num = v[0].first;
int short_idx = v_temp[0].second;
oil -= short_num;
long long dist = bfs2(short_idx);
if(dist==-1){ // 중간에 연료가 부족하거나, 도착할 수 없다.
check_final = false;
}else{
m--;
check[short_idx] = 1;
oil = oil-dist+2*dist;
//택시 출발 지점 바꿔주기
start_x = customer[short_idx].second.first;
start_y = customer[short_idx].second.second;
}
}
int main()
{
cin>>n>>m>>oil;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
cin>>road[i][j];
}
}
cin>>start_x>>start_y;
for(int i=0; i<m; i++){
cin>>s_x>>s_y>>e_x>>e_y;
customer.push_back(make_pair(make_pair(s_x, s_y), make_pair(e_x, e_y)));
}
while(1){
check_final = true;
bfs();
if(m==0){ // 모든 승객을 다 태웠다.
break;
}
if(check_final==false){ // 중간에 연료가 없거나 다 태울 수 없는 경우
break;
}
// break;
}
if(check_final==false){
cout<<"-1"<<"\n";
}else{
cout<<oil<<"\n";
}
return 0;
}
|
cs |
문제 첨부
https://www.acmicpc.net/problem/19238
github 첨부(https://github.com/jungahshin/algorithm/blob/master/c:c%2B%2B/19238.cpp)
반응형
'Algorithm > 삼성 sw 역량테스트 기출' 카테고리의 다른 글
[Algorithm] 삼성전자 코딩테스트 - 구슬 탈출 2(c++) (0) | 2020.09.21 |
---|---|
[Algorithm] 2020 상반기 삼성전자 코딩테스트 오전 - 모노미노도미노(c++) (0) | 2020.09.17 |
[Algorithm] 2018 하반기 삼성전자 코딩테스트 - 나무재테크(c++) (0) | 2020.09.17 |
[Algorithm] 2020 상반기 삼성전자 코딩테스트 오전 - 청소년 상어(c++) (0) | 2020.07.29 |
[Algorithm] 2020 상반기 삼성전자 코딩테스트 오후 - 어른 상어(c++) (0) | 2020.07.19 |
Comments