[programmers] 340211번 - 충돌위험 찾기 (구현, [PCCP 기출문제] 3번)

1. 문제 및 예제

 

문제를 제대로 읽지 않아 두바퀴 정도 뺑뺑 돌다가 해결한 문제다. 아까운 내 한 시간이 날아갔다. 이렇게 장문의 문제를 푸는 요령이라도 터득해야할 것 같다. 집중력 문제인 것 같기도해서 최근에는 시간을 정해두고 문제를 풀고있다. 이런 구현 문제는 지금 회사에서도 비슷한 일을 하는데 이렇게 시간이 오래 걸리다니... 충격적이긴 하다 ㅋㅋ

---

https://school.programmers.co.kr/learn/courses/30/lessons/340211

프로그래머스

---

2. 본론

 

이런 복잡한 문제들은 문제를 나누고 그 개념을 명확하게 나누는 것이 중요하다. 그럼 버그가 잘 안 생기고 생겨도 버그를 찾기 쉬워진다. 요즘엔 구현문제가 너무 많이 나오는데 구현문제의 중요한점은 "얼마나 빠른 시간동안 해결하냐" 인 것 같다. 그리고 내가 지금까지 경험한 바로는 빠른 시간안에 문제를 해결하기 위해서는 클린코드로 작성하는 것이 가장 효율적이다.

 

문제는 다음과 같이 나눴다.

---

1. 로봇의 초반 위치를 셋팅한다.

2. 로봇이 겹친 위치를 계산한다.

3. 로봇의 위치를 업데이트한다.

4. 모든 로봇이 사라질 때 까지 2번 3번 반복.

---

목적 포인트가 하나가 아닐 수 있기 때문에(이것 때문에 한 시간 날렸다. 예시 3번을 안 봤다...) 목적포인트와 지금 로봇의 좌표를 가지고 있어야한다. 이문제를 푸는 방법을 보면 3차원 배열을 사용하는데 이는 그렇게 효율적이지 않다고 생각해서 그냥 로봇의 위치만을 정하는 배열을 만들었다.

 

vector<pair<int, pair<int, int>>> coordinate;
    
// 로봇 배치
for(int i = 0; i < routes.size(); i++){
    int start_point = routes[i][0];
    int r = points[start_point - 1][0];
    int c = points[start_point - 1][1];
    coordinate.push_back(make_pair(1 , make_pair(r, c)));
}

 

로봇이 겹친 위치를 계산하는 법은 배열을 사용했다. 이렇게 되면 로봇의 수 만큼의 시간복잡도를 가지게 된다. 배열이 없다면 대충 계산해봤을 때 O(N^2)정도 돌게 되어서 배열을 사용했다.

 

int count_crash(vector<pair<int, pair<int, int>>> coordinate){
    int board[105][105] = {0};
    int count = 0;
    
    for(auto it : coordinate){
        if(it.second.first != -1 && it.second.second)
            board[it.second.first][it.second.second]++;
    }
    
    for(int i = 0; i < 105; i++){
        for(int j = 0; j < 105; j++){
            if(board[i][j] > 1){
                count++;
            }
        }
    }
    return count;
}

 

로봇을 움직이는 코드는 간단하다. X좌표와 Y좌표를 따라가기만 하면 된다. 다만 X좌표를 먼저 움직이기만 하면 된다. 만약 목적지에 도착했다면 목표를 다음으로 옮기면 된다.

 

vector<pair<int, pair<int, int>>> update_coordinate(
    vector<pair<int, pair<int, int>>> coordinate, 
    vector<vector<int>> points, 
    vector<vector<int>> routes)
    {
    
    vector<pair<int, pair<int, int>>> new_coordinate;
    
    for(int i = 0; i < coordinate.size(); i++){
        
        int cur_target_index = coordinate[i].first;
        int cur_row = coordinate[i].second.first;
        int cur_col = coordinate[i].second.second;

        if(cur_target_index != -1){
            int target_point = routes[i][cur_target_index];
            int target_row = points[target_point - 1][0];
            int target_col = points[target_point - 1][1];
        
            if(cur_row != target_row){
                
                if(cur_row < target_row)
                    cur_row++;
                else
                    cur_row--;
            
            }else if(cur_col != target_col){
                if(cur_col < target_col)
                    cur_col++;
                else
                    cur_col--;  
            }
            
            if(cur_row == target_row && cur_col == target_col){
                cur_target_index++;

                if(cur_target_index == routes[i].size())
                    cur_target_index = -1;
            }
        }else{
            cur_row = -1;
            cur_col = -1;
        }
        new_coordinate.push_back(make_pair(cur_target_index, make_pair(cur_row, cur_col)));
    }
    
    return new_coordinate;
}

 

다음은 전체 코드이다.

 

#include <string>
#include <vector>
#include <utility>
#include <iostream>

using namespace std;

bool is_system_end(vector<pair<int, pair<int, int>>> coordinate){
    for(auto it : coordinate){
        if(it.second.first != -1 || it.second.second != -1)
            return false;
    }
    return true;   
}

int count_crash(vector<pair<int, pair<int, int>>> coordinate){
    int board[105][105] = {0};
    int count = 0;
    
    for(auto it : coordinate){
        if(it.second.first != -1 && it.second.second)
            board[it.second.first][it.second.second]++;
    }
    
    for(int i = 0; i < 105; i++){
        for(int j = 0; j < 105; j++){
            if(board[i][j] > 1){
                count++;
            }
        }
    }
    return count;
}

vector<pair<int, pair<int, int>>> update_coordinate(
    vector<pair<int, pair<int, int>>> coordinate, 
    vector<vector<int>> points, 
    vector<vector<int>> routes)
    {
    
    vector<pair<int, pair<int, int>>> new_coordinate;
    
    for(int i = 0; i < coordinate.size(); i++){
        
        int cur_target_index = coordinate[i].first;
        int cur_row = coordinate[i].second.first;
        int cur_col = coordinate[i].second.second;

        if(cur_target_index != -1){
            int target_point = routes[i][cur_target_index];
            int target_row = points[target_point - 1][0];
            int target_col = points[target_point - 1][1];
        
            if(cur_row != target_row){
                
                if(cur_row < target_row)
                    cur_row++;
                else
                    cur_row--;
            
            }else if(cur_col != target_col){
                if(cur_col < target_col)
                    cur_col++;
                else
                    cur_col--;  
            }
            
            if(cur_row == target_row && cur_col == target_col){
                cur_target_index++;

                if(cur_target_index == routes[i].size())
                    cur_target_index = -1;
            }
        }else{
            cur_row = -1;
            cur_col = -1;
        }
        new_coordinate.push_back(make_pair(cur_target_index, make_pair(cur_row, cur_col)));
    }
    
    return new_coordinate;
}

int solution(vector<vector<int>> points, vector<vector<int>> routes) {
    int answer = 0;
    vector<pair<int, pair<int, int>>> coordinate;
    
    // 로봇 배치
    for(int i = 0; i < routes.size(); i++){
        int start_point = routes[i][0];
        int r = points[start_point - 1][0];
        int c = points[start_point - 1][1];
        coordinate.push_back(make_pair(1 , make_pair(r, c)));
    }
    
    while(!is_system_end(coordinate)){
        
        //result count
        int count = count_crash(coordinate);
        answer += count;
        
        //update coordinate
        coordinate = update_coordinate(coordinate, points, routes);        
    }
    
    return answer;
}

 

3. 결어

 

지금 직장에서 하는 일이 거의 구현문제를 푸는 일처럼 느껴져서 구현 문제 보다는 DP를 많이 풀고 있었는데 오늘 한 실수가 너무 충격적이었다. 앞으로는 그냥 눈에 띄는 대로 문제를 풀어봐야겠다.