https://programmers.co.kr/learn/courses/30/lessons/60062
코딩테스트 연습 - 외벽 점검
레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하
programmers.co.kr
풀이
처음 문제를 O(N)만에 풀 수 있는 방법을 생각해보았지만 뜻대로 되지 않고 자꾸 DFS를 이용하는 방법이 떠올라 DFS를 이용하지 않고 풀어보려했지만 결국 DFS를 사용하게 되었다. 이 문제가 까다로운 부분은 원형으로 연결되어 있다는 것이다. 1차원 배열의 맨 끝에서 오른쪽으로 한 번 더 이동하면 첫 번째 원소에 와야하는 것과 같은 예외처리를 해야한다. 문제는 다음과 같이 풀었다.
- DFS를 이용하여 임의의 취약지점에서 출발한다.
- 점검할 수 있는 취약지점까지 점검한다.
- 다음 취약지점부터 아직 점검하지 않은 친구가 점검할 수 있는 거리만큼 점검한다.
- 만약 점검한 취약지점 수와 전체 취약지점 수가 같은 경우 결과값을 최소값으로 갱신한다.
소스 코드
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int answer = 1e9; //정답 최대값으로 설정
int N;
vector<bool> dvisit; //점검을 완료한 친구 표시
void dfs(int ans, int now, int len, int total, vector<int> &weak, vector<int> &dist) {
int start = weak[now]; //시작 취약지점
int limit = weak[now] + dist[len]; //점검할 수 있는 거리의 마지노선
int cnt = 0; //점검한 취약지점 수
if(limit >= N) { //만약 범위를 벗어나 다시 0부터 시작하는 경우
while(true) {
if((weak[now] >= start) || (weak[now] <= (limit % N))) { //다음 탐색할 취약지점이 점검할 수 있는 범위에 있는 경우
now++; //다음 취약지점으로 이동
now %= weak.size(); //범위 벗어나지 않게 처리
cnt++; //점검한 취약지점 수 증가
if(cnt + total == weak.size()) { //취약지점 모두 점검한 경우
answer = min(answer,ans); //최소값 갱신
return; //리턴
}
}
else { //범위를 벗어난 경우 점검 종료
break;
}
}
}
else { //만약 범위를 벗어나지 않는 경우
while(true) {
if((weak[now] >= start) && (weak[now] <= limit)) { //다음 탐색할 취약지점이 점검할 수 있는 범위에 있는 경우
now++; //다음 취약지점으로 이동
now %= weak.size(); //범위 벗어나지 않게 처리
cnt++; //점검한 취약지점 수 증가
if(cnt + total == weak.size()) { //취약지점 모두 점검한 경우
answer = min(answer,ans); //최소값 갱신
return; //리턴
}
}
else { //범위를 벗어난 경우 점검 종료
break;
}
}
}
for(int d = 0; d < dist.size(); d++) { //점검할 다음 친구 선택
if(dvisit[d]) continue; //이미 점검한 친구는 패스
dvisit[d] = true; //방문표시
dfs(ans+1 , now, d, total + cnt, weak, dist); //DFS를 이용하여 now부터 취약지점 점검
dvisit[d] = false; //방문표시 취서
}
}
int solution(int n, vector<int> weak, vector<int> dist) {
N = n; //외벽길이 전역변수로 저장
dvisit.resize(dist.size()); //방문배열 크기 설정
sort(dist.begin(), dist.end(), greater<int>()); //큰 것부터 정렬
for(int w = 0; w < weak.size(); w++) { //점검을 시작할 취약지점 위치
for(int d = 0; d < dist.size(); d++) { //점검할 친구 선택
dvisit[d] = true;
dfs(1, w, d, 0, weak, dist);
dvisit[d] = false;
}
}
if(answer == 1e9) return -1; //모두 탐색하지 못한 경우 -1 리턴
else return answer; //그렇지 않은 경우 최소값 리턴
}최대한 반복되는 비교를 하지 않도록 방문함수를 설정하고 점검한 취약지점을 다시 점검하도록 하지 않도록 다음 취약지점으로 이동하며 점검하도록 프로그램을 짜보았다. DFS함수의 인자가 많은 것이 아쉬운 부분이지만 다른 방법으로는 떠오르지 않아 함수의 인자 밖에 선택할 수 없었다. weak와 dist를 모두 전역변수로 하면 메모리 낭비와 복사하는 시간이 걸리므로 call by reference를 이용하여 그런 시간을 줄여보았다.
채점 결과
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [C++] 프로그래머스 블록 이동하기 풀이 (0) | 2021.08.18 |
|---|---|
| [C++] 프로그래머스 매칭 점수 풀이 (0) | 2021.08.12 |
| [C++] 프로그래머스 순위 검색 풀이 (0) | 2021.08.06 |
| [C++] 프로그래머스 110 옮기기 풀이 (0) | 2021.08.06 |
| [C++] 프로그래머스 모두 0으로 만들기 풀이 (3) | 2021.08.05 |
