22.06.14. 풀었던 문제들

1. 블록 이동하기

어제 시간 없어서 못 풀었던 문제 풀었다. 전체적으로 구현이 귀찮은 문제였다. 신경 쓸 것도 많았고.

로직 자체는 간단한 BFS이지만

​

1) visited 배열 - 로봇의 위치는 점 2개로 이루어지기 때문에 점 2개를 이용해서 중복 검사를 할 수 있게 해야 했기 때문에 ppiipii를 항상 정렬한 상태로 유지했다.

2) 이동 가 / 불 여부 - 현재 위치 (r, c), (r', c') 기준으로 어디로 이동할 수 있는가?를 조금 생각해 주어야 했다.

a) 직선 이동하는 경우 - 위 / 아 / 왼 / 오 - 모두 다 범위 안이고 0이어야 이동할 수 있음. 이건 쉽지만

b) 회전 이동하는 경우 - (r, c)을 축으로 90도 - 이게 귀찮았다. 물론 이동 후 위치도 0이어야 이동 가능하겠지?

가로 : (r, c)와 (r', c')에서 축이 (r, c)인 경우

(r+1, c)와 (r-1, c)로 갈 수 있음

(r+1, c)로 가는 경우 : (r+1, c')가 1인지 검사해야 함

(r-1, c)로 가는 경우 : (r-1, c')가 1인지 검사해야 함

세로 : (r, c)와 (r', c')에서 축이 (r, c)인 경우

(r, c+1)와 (r, c-1)로 갈 수 있음

(r, c+1)로 가는 경우 : (r', c+1)가 1인지 검사해야 함

(r, c-1)로 가는 경우 : (r', c-1)가 1인지 검사해야 함

​

// 블록 이동하기

#include <string>
#include <vector>
#include <set>
#include <queue>
#include <iostream>

using namespace std;

int N;
typedef pair<int, int> pii;
typedef pair<pii, pii> ppiipii; //drone 위치

bool cmp(pii &a, pii &b){
    if(a.first == b.first){
        return a.second < b.second;
    }
    return a.first < b.first;
}

void sort_ppiipii(ppiipii &a){
    if(!cmp(a.first, a.second)){
        pii temp = a.first;
        a.first = a.second;
        a.second = temp;
        return;
    }
    return;
}

void rotate(vector<vector<int>>& board, pii mov, pii axis, bool isVertical, vector<ppiipii>& result){
    if(isVertical){ // 세로
        if(axis.second + 1 < N && board[mov.first][axis.second+1] == 0 && board[axis.first][axis.second + 1] == 0){
            result.push_back({axis, {axis.first, axis.second + 1}});
        }
        if(axis.second - 1 >= 0 && board[mov.first][axis.second-1] == 0 && board[axis.first][axis.second - 1] == 0){
            result.push_back({axis, {axis.first, axis.second - 1}});
        }
    }
    else{ // 가로
        if(axis.first + 1 < N && board[axis.first + 1][mov.second] == 0 && board[axis.first + 1][axis.second] == 0){
            result.push_back({axis, {axis.first + 1, axis.second}});
        }
        if(axis.first - 1 >= 0 && board[axis.first - 1][mov.second] == 0 && board[axis.first - 1][axis.second] == 0){
            result.push_back({axis, {axis.first - 1, axis.second}});
        }
    }
}
/*
 가로 : (r, c)와 (r', c')에서 축이 (r, c)인 경우
            (r+1, c)와 (r-1, c)로 갈 수 있음
            (r+1, c)로 가는 경우 : (r+1, c')가 1인지 검사해야 함
            (r-1, c)로 가는 셩우 : (r-1, c')가 1인지 검사해야 함
 세로 : (r, c)와 (r', c')에서 축이 (r, c)인 경우
            (r, c+1)와 (r, c-1)로 갈 수 있음
            (r, c+1)로 가는 경우 : (r', c+1)가 1인지 검사해야 함
            (r, c-1)로 가는 경우 : (r', c-1)가 1인지 검사해야 함*/

vector<ppiipii> moveablePosition(vector<vector<int>>& board, ppiipii &cur_position){
    vector<ppiipii> result;
    pii blue = cur_position.first, red = cur_position.second;
    if(blue.first + 1 < N && board[blue.first + 1][blue.second] == 0 && red.first + 1 < N && board[red.first + 1][red.second] == 0){ // 하
        result.push_back({{blue.first+1, blue.second}, {red.first+1, red.second}});
    }
    if(blue.first - 1 >= 0 && board[blue.first - 1][blue.second] == 0 && red.first - 1 >= 0 && board[red.first - 1][red.second] == 0){ // 상
        result.push_back({{blue.first-1, blue.second}, {red.first-1, red.second}});
    }
    if(blue.second + 1 < N && board[blue.first][blue.second + 1] == 0 && red.second + 1 < N && board[red.first][red.second + 1] == 0){ // 우
        result.push_back({{blue.first, blue.second + 1}, {red.first, red.second + 1}});
    }
    if(blue.second - 1 >= 0 && board[blue.first][blue.second - 1] == 0 && red.second - 1 >= 0 && board[red.first][red.second - 1] == 0){ // 좌
        result.push_back({{blue.first, blue.second - 1}, {red.first, red.second - 1}});
    }
    
    bool isVertical = blue.second == red.second;
    rotate(board, blue, red, isVertical, result);
    rotate(board, red, blue, isVertical, result);
    for(int i = 0; i<result.size(); i++){
        sort_ppiipii(result[i]);
    }
    return result;
}

bool isArrive(ppiipii& cur_position){
    pii blue = cur_position.first, red = cur_position.second;
    if((blue.first == N-1 && blue.second == N-1) || (red.first == N-1 && red.second == N-1)) return true;
    else return false;
}

int solution(vector<vector<int>> board) {
    N = board.size();
    
    ppiipii drone = {{0, 0}, {0, 1}}; // .first : 첫 번째 점, .second : 두 번째 점
    
    set<ppiipii> visited;
    sort_ppiipii(drone);
    visited.insert(drone);
    
    queue<pair<ppiipii, int>> q; // .first : 현재 드론 위치 ppiipii, .second : 해당 위치의 dist
    q.push({drone, 0});
    
    while(!q.empty()){
        ppiipii cur_position = q.front().first;
        int cur_dist = q.front().second;
        
        /*cout<<"점, dist : "<<cur_dist<<endl;
        cout<<"blue : "<<cur_position.first.first<<", "<<cur_position.first.second<<endl;
        cout<<"red : "<<cur_position.second.first<<", "<<cur_position.second.second<<endl;
        cout<<endl;*/
        
        q.pop();
        vector<ppiipii> moveable = moveablePosition(board, cur_position);
        for(ppiipii& m : moveable){
            
            if(isArrive(m)){
                return cur_dist + 1;
            }
            
            sort_ppiipii(m);
            
            if(visited.find(m) == visited.end()){ // not visited
                visited.insert(m);
                q.push({m, cur_dist + 1});
            }
        }
    }
    return -1;
}

/*

BFS인데 신경 쓸 게 많은...
1) visited 배열 - 현재 로봇의 위치는 점 2개로 이루어지니 이들의 중복 검사를 할 수 있게 해야 함
2) 이동하는 경로 - 현재 위치 (r, c), (r', c') 기준으로 어디로 이동할 수 있는가?
  a) 직선 이동하는 경우 - 위 / 아 / 왼 / 오 - 모두 다 범위 안이고 0이어야 이동할 수 있음
  b) 회전 이동하는 경우 - (r, c)을 축으로 90도

 가로 : (r, c)와 (r', c')에서 축이 (r, c)인 경우
            (r+1, c)와 (r-1, c)로 갈 수 있음
            (r+1, c)로 가는 경우 : (r+1, c')가 1인지 검사해야 함
            (r-1, c)로 가는 셩

 

 

2. 매칭 점수

string의 find 함수를 이용하면 너무너무 쉽게 풀 수 있다. string.find(target, start_index) == string::npos 인 경우에는 string의 start_index부터 target을 찾아서 string::npos면 못 찾은 것이다. 이거 정리해 보자.

일단 알고리즘의 경우에는 page를 받아서 해당 page에서 뽑을 수 있는 모든 정보(해당 page 이름, 참조하는 외부 링크 vector 및 그 숫자(href 개수), 해당 page의 기본 점수(word에 해당하는 문자 검사 - word를 찾으면 앞뒤로 alphabet이 아닌지 확인해야 한다) 등을 뽑아 구조체에 넣었다. 이렇게 첫 번째 for문을 돌리고 mapper를 만들어 이름-index mapping을 했다. 이후는 쉽다. page의 href vector마다 (basic 점수 / 참조 개수)만큼 더해주고, 정렬하면 끝이다.

// 매칭 점수

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>

using namespace std;

struct webdata{
    int index, basic_point, num_external_link;
    double link_point;
    string pagename;
    vector<string> hrefs;
};

bool cmp(webdata &a, webdata &b){
    if(a.link_point + a.basic_point == b.link_point + b.basic_point){
        return a.index < b.index;
    }
    else return a.link_point + a.basic_point > b.link_point + b.basic_point;
}

webdata summary(string word, string page){
    webdata wd; wd.index = wd.basic_point = wd.num_external_link = wd.link_point = 0;
    wd.pagename = "";
    
    // 해당 page 이름 뽑기
    string metatag = "<meta property=\"og:url\" content=\"";
    int pagename_start_idx = page.find(metatag) + metatag.length();
    int metatag_end_idx = page.find("\"/>", pagename_start_idx);
    wd.pagename = page.substr(pagename_start_idx, metatag_end_idx - pagename_start_idx);
    
    // 해당 page가 참조하는 외부 링크(및 그 수) 뽑기
    int hreftag_start_idx = 0, hreftag_end_idx = 0;
    string hreftag = "<a href=\"";
    while(1){
        hreftag_start_idx = page.find(hreftag, hreftag_end_idx);
        if(hreftag_start_idx == string::npos) break;
        hreftag_start_idx += hreftag.length();
        hreftag_end_idx = page.find("\">", hreftag_start_idx);
        wd.num_external_link++;
        wd.hrefs.push_back(page.substr(hreftag_start_idx, hreftag_end_idx - hreftag_start_idx)); // 참조하는 링크
    }
    
    // 해당 page의 기본 점수(word에 해당하는 문자열) 뽑기
    for(char& c : page) c = tolower(c);
    for(char& c : word) c = tolower(c);
    int word_start_idx = 0, wordsize = word.size(), pagesize = page.size();
    while(1){
        word_start_idx = page.find(word, word_start_idx);
        if(word_start_idx == string::npos) break;
        if(word_start_idx + wordsize >= pagesize
           || (word_start_idx - 1 >= 0 && !isalpha(page[word_start_idx - 1]) && word_start_idx + wordsize < pagesize && !isalpha(page[word_start_idx + wordsize]))){
            wd.basic_point++;
        }
        word_start_idx++;
    }
    
    return wd;
}

int solution(string word, vector<string> pages) {
    map<string, int> mapper; // mapper[string] : string에 해당하는 pages index
    vector<vector<int>> adjacent(21, vector<int>(21, 0)); // adjacent[i][j] : i에서 j를 호출하는 갯수
    vector<webdata> v(pages.size());
    
    for(int i = 0; i<pages.size(); i++){
        webdata wd = summary(word, pages[i]);
        wd.index = i;
        mapper[wd.pagename] = i;
        v[i] = wd;
    }
    
    for(int i = 0; i<v.size(); i++){
        double link_point = (double)v[i].basic_point / (double)v[i].num_external_link;
        for(string& h : v[i].hrefs){
            if(mapper.find(h) != mapper.end())
                v[mapper[h]].link_point += link_point;
        }
        
        cout<<endl;
    }
    
    sort(v.begin(), v.end(), cmp);
    
    return v[0].index;
}

/*

기본 점수 : text 중 검색어가 등장하는 횟수(대소문자 무시)
외부 링크 수 : 해당 페이지에서 다른 웹페이졸 연결된 링크 개수
링크 점수 : 해당 웹페이지로 링크걸린 다른 웹페이지의 기본점수 / 해당 웹페이지의 외부 링크 수의 총 합

*/