문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/60062#
카카오 코딩 테스트에 나왔던 문제다.
확실히 문제 이해하기도 복잡하다.
문제 핵심 및 풀이
유형 유추
제한 조건에 보면 외벽의 최대 길이(n)는 200까지이다.
인원을 배치할 수 있는 경우의 수는 200가지이다.
인원은 최대 8명까지 가능하다.
그리고 결함이 있는 외벽도 15개까지밖에 주어지지 않는다.
계산에 필요한 인원, 외벽, 최대 길이가 굉장히 짧다.
O(n^2)을 하더라도 충분하고 O(n^3)도 가능하다.
그래서 완전 탐색이 사용가능하다고 생각했다.
어떻게 하면 외벽 점검을 최소의 인원만 사용할 수 있을까
해당 문제에서 키워드는 외벽이 원형 모양이라는 것이다.
이 말은 외벽을 설계할 때,
마지막에서 처음으로 돌아갈 수 있게 설계를 해야 한다는 것이다.
(원형 큐 구현하는 것처럼)
일단 인원을 고르는 문제 전에,
한 사람이 움직이는 것에 대해 생각해 봤다.
1. 선택된 사람의 출발 지점을 어디로 해야 하는가?
2. 움직이는 선택지가 2개(반시계 / 시계 방향)
출발 지점을 어디로 해야 하는가?
한 사람을 배치할 때 어디로 둬야 하는가?
외벽 길이가 n이라면 n개의 위치에 둘 수 있다.
가장 이득이 되도록 하려면, 출발지점을 결함이 있는 외벽으로 잡아야 한다.
외벽에서 출발하면 움직임을 소모하지 않고도,
하나는 바로 고칠 수 있으니까..
움직이는 선택지를 고려해야 하는가?
움직이는 방향에 대해서 고민했는데, 생각해 보니 상관없었다.
위 그림처럼 한 사람은 시계방향, 다른 사람은 반시계 방향으로 움직인다면
둘의 탐색 범위가 겹치게 된다.
탐색 범위가 겹치는 것은 움직이는 거리를 낭비하는 것이기 때문에,
인원을 최소한으로 사용할 수 없다.
최소의 인원만을 사용하려면, 외벽을 최대한 많이 봐야 한다.
그러니까 총 움직이는 거리가 최대가 돼야 한다는 것이다.
그래서 애초에 한쪽 방향으로만 움직이면 겹침을 최소화한다.
놓는 위치가 겹치지 않고 한쪽 방향으로만 움직이면 움직이면서 겹칠 일이 없다.
결론
위의 2가지를 합쳐보면,
시작 위치는 외벽 결함이 있는 곳으로 배치하고,
모든 사람의 움직임을 한쪽 방향으로 통일한다.
사람을 고르는 방법
이제 다음 문제는 어떤 사람을 골라야 하냐는 것이다.
간단하게는 움직일 수 있는 거리가 긴 사람부터 쓰면 될 것 같지만,
이렇게 되면 최대 효율로 탐색을 못하는 경우가 있다.
만약 많이 움직일 수 있는 사람을 먼저 사용하면,
저런 식으로 효율적이지 못한 위치에 둘 수가 있다.
그래서 많이 움직이는 순서대로 배치하면 안 된다.
근데 그렇다고 짧은 걸 먼저 둘 수도 없는 노릇이다.
근데 여기서 중요한 것은 사람은 최대 8명이라는 것이다.
즉 8명으로 나올 수 있는 순서의 경우의 수는 8! = 40320개밖에 안된다.
어차피 탐색할 외벽도 최대 200까지 밖에 되지 않기 때문에 시간은 충분하다.
그래서 백트래킹을 통해 배치 순서의 모든 경우의 수를 구했다.
외벽 중 어느 위치에 배치해야 하나?
사람의 순서는 모든 경우의 수를 구하는 것으로 가능할 것 같은데,
그럼 이제 어느 외벽에 두냐는 것이 문제이다.
일단 이미 발견한 외벽엔 배치하면 당연히 안된다.
그렇다고 인원을 정하는 순서처럼 모든 경우를 구하자니
15! x 8! = 1,307,674,368,000로 바로 시간초과다..
결론은 가장 처음에 배치할 외벽 지점만 고려해 주면 된다.
왜냐하면 이미 인원 순서에 대한 모든 경우의 수를 구해놨기 때문이다.
인원이 2명만 있다고 가정하고,
가장 위(12시 방향)에서 출발할 때 나올 수 있는 모든 경우를 보자.
순서를 바꾸는 것만으로도 서로의 출발지가 달라진다.
왼쪽 경우는 초록색이 12시, 파란색이 6시에서 출발한다.
오른쪽은 초록색이 11시 방향, 파란색이 12시로 다르다.
이렇게 인원 순서에 따라 자동으로 외벽을 선택하는 순서가 정해진다.
그리고 한 사람이 이동이 끝나면,
다음 사람이 출발하는 위치는 그 바로 옆에 있는 외벽지점으로 정하고 있다.
이는 어차피 모든 결함을 해결해야 하기 때문이다.
그래서 다음 사람의 출발 지점을 정하는 경우의 수는 고려하지 않아도 된다.
바로 옆이 아닌 다른 지점에서 출발한다고 해도,
어차피 모든 결함을 해결해야 하니까
결국엔 누군가는 그 지점을 방문해야만 한다.
그래서 첫 사람의 출발 지점을 정하는 수만 고려해도
모든 경우의 수를 알 수 있다.
외벽 결함의 최대 개수가 15이니까 나올 수 있는 경우의 수는
8! x 15 밖에 되지 않아 시간초과가 나지 않는다.
그렇기 때문에 인원 배치에 대한 순서와
외벽 결함 지점의 경우의 수만 고려해 주면 된다.
실수하기 쉬운 부분
배치 순서와 출발지를 정했으면
이제 실제로 시뮬레이션을 돌려보면 된다.
여기서 주의해야 할 점은 이미 발견했던 결함 지점은
제외해줘야 한다는 것이다.
자바로 이를 구현할 때 List를 보통 쓰는데,
얕은 참조가 되지 않도록 주의해야 한다.
또한 원을 구현해야 하기 때문에
인덱싱을 하는 과정에서 배열 밖으로 벗어나는 것을 주의한다.
코드 구현
C++ 구현 코드
↓
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
vector<int> weaks,dists; // 전역변수화
vector<vector<int>> orders; // 인원 배치 순서를 담는 벡터
bool visited[8] = {false,}; // 인원 중복 방문 방지하기 위한 배열
int len; // 외벽의 길이(n)
// 백트래킹을 통해 인원 배치 순서의 모든 경우의 수를 orders에 저장
void backtracking(vector<int> list){
// list 크기가 전체 인원과 같다면 종료
if(list.size() == dists.size()){
orders.push_back(list); 해당 순서를 orders에 저장
return;
}
// 백트래킹
for(int i = 0; i < dists.size(); i++){
if(visited[i]) continue;
visited[i] = true;
list.push_back(dists[i]);
backtracking(list);
visited[i] = false;
list.pop_back();
}
}
int simulation(vector<int> order, int start){
bool checked[15]; // 외벽 지점 중복 방지를 위해
int cnt = 0; // 다음 번째 순서를 호출을 위한 인덱스
fill(checked,checked+15,false); // 초기화
for(int k = start; k < weaks.size(); k++){
if(cnt >= dists.size()) break; // out of bound 방지
if(checked[k]) continue; // 이미 방문한 지점 패스
int sPos = weaks[k];
// 해당 외벽 지점에서 시작하여 이동거리만큼 감
for(int j = sPos; j <= sPos+order[cnt]; j++){
int pos = j % len; // 원형 구현을 위해 모듈러 연산
// weaks 벡터에서 pos가 있는지 확인
auto it = find(weaks.begin(),weaks.end(),pos);
if(it != weaks.end()){
// 존재하면 해당 인덱스 방문처리
int idx = it - weaks.begin();
checked[idx] = true;
}
}
cnt++; // 다음 순서의 사람을 불러옴
}
// 방문되지 않은 지점이 하나라도 있으면 실패
for(int i = 0; i < weaks.size(); i++){
if(!checked[i]) return 999;
}
return cnt; // 인덱스가 곧 횟수
}
int solution(int n, vector<int> weak, vector<int> dist) {
len = n;
weaks = weak;
dists = dist;
vector<int> tmp;
backtracking(tmp);
int answer = 999;
// 모든 인원 배치 순서에 따른 반복
for(auto order : orders){
// 해당 지점을 출발지로 simulation 함수 호출
for(int i = 0; i < weak.size(); i++){
answer = min(answer,simulation(order,i));
}
}
answer = (answer == 999)? -1 : answer; // 실패하면 -1 반환
return answer;
}↑
Java 구현 코드
↓
import java.util.ArrayList;
import java.util.List;
class Solution {
static int size = 0; // 외벽의 크기(n)
// 백트래킹을 위해 사람에 대한 방문 배열을 만듦
static boolean[] visited = new boolean[8];
static int[] weaks, dists; // 전역변수화
static List<List<Integer>> orders = new ArrayList<>(); // 모든 순서를 담을 배열
// 백트래킹으로 인원 배치 순서에 대한 모든 경우의 수를 구한다.
void getOrder(List<Integer> list) {
// 리스트 크기가 인원 배열과 같다는 것은 탐색 끝을 의미
if (list.size() >= dists.length) {
orders.add(list); // 해당 순서를 리스틍 넣어줌
return;
}
// 백트래킹
for (int i = 0; i < dists.length; i++) {
if (visited[i]) continue; // 이미 방문한 곳 다시 방문하지 않도록
visited[i] = true;
list.add(dists[i]);
// 리스트의 주소값이 같아지는 것을 막기 위해 새로운 arrayList 생성
getOrder(new ArrayList<Integer>(list));
visited[i] = false;
// 위에서 리스트에서 추가해준 것 삭제
list.remove(list.size() - 1);
}
}
// 시뮬레이션 돌리는 함수(인원 배치 순서 중 하나, 시작 외벽 지점)
int simulation(List<Integer> order, int start) {
// 이미 방문했던 외벽 지점 중복 방문을 막기위해 방문 배열 생성
boolean[] check = new boolean[weaks.length];
int cnt = 0; // 사람 번호를 나타내는 인덱스
for (int i = start; i < weaks.length; i++) {
if (check[i]) continue;
if (cnt >= order.size()) break; // out of bound 방지
int sPos = weaks[i];
// 해당 지점에서 이동거리 만큼 이동하면서 결함 확인
for (int j = sPos; j <= sPos + order.get(cnt); j++) {
int pos = j % size; // 원형을 구현하기 위해 모듈러 연산
// 해당 지점에 결함이 있는지 확인하고, 있으면 check
for (int k = 0; k < weaks.length; k++) {
if (weaks[k] == pos) check[k] = true;
}
}
cnt++; // 다음 사람을 불러오기 위해 인덱스+1
}
// 결함이 하나라도 남아있다면 실패
for (int i = 0; i < weaks.length; i++) {
if (!check[i]) return 999;
}
return cnt;
}
public int solution(int n, int[] weak, int[] dist) {
weaks = weak;
dists = dist;
size = n;
getOrder(new ArrayList<Integer>());
int answer = 999;
for (List<Integer> order : orders) {
// 인원배치 모든 경우의 수에 첫 외벽 위치를 정해 시뮬레이션을 돌림
for (int i = 0; i < weak.length; i++) {
answer = Math.min(answer, simulation(order, i));
}
}
// 999가 나왔다는 것은 실패를 의미
if (answer == 999) answer = -1;
return answer;
}
}↑
시행착오
1시간 안에 푸는 건 실패했다.
해당 문제가 완전 탐색인건 알았는데,
외벽 순서까지 백트래킹을 해버려서 시간초과가 나왔다.
좀만 더 깊게 생각했으면 외벽 순서는 필요 없다는 걸 알았을 텐데 아쉽다.
거의 다 푼 것 같은데, 뭔가 논리적으로 꼬였다.
howudong님에게 보내주세요
토스아이디로 안전하게 익명 송금하세요.
toss.me