22.06.17. 풀었던 문제들

1. 백준 1717 집합의 표현

union-find 기초 구현 문제

​

​

2. 사라지는 발판

첫 접근은 - A, B 둘 다 이동할 수 있는 경로로 이동하되 전체 게임의 수가 제일 긴 것을 리턴하게 했는데... 이러면 A가 이길 수 있는 상황에서도 지는 경우로 가는 수가 생긴다. 즉 잘못된 풀이다.

잘 모르겠어서 구글링 한 결과 접근은 아래와 같다.

​

• 현재 플레이어가 어떤 수를 택하고, 다음 플레이어가 어떤 수를 택했을 때
  • 다음 플레이어가 승리 가능한 수가 있을 때 : 승리할 수 있는 수를 선택할 것이다.
  • 다음 플레이어가 무조건 패배할 때 : 최대한 게임을 길게 끌고 갈 것이다.
• 종료 조건은 더 이상 움직이지 못할 때, 승리자는 현 플레이어가 아닌 플레이어이다.

에서 시작한다.

​

위 접근으로, '현 플레이어'가 움직일 수 있는 모든 경우의 수AChoice에서

• '다른 플레이어'가 어떠한 수를 두어도 '다른 플레이어'가 패배한다면 그 경우를 택하면 된다. 만약 그 경우의 수AChoice가 여러개라면 더 일찍 끝나는 경우의 수를 택하면 된다.
• '다른 플레이어'가 어떠한 수를 두어도 '다른 플레이어'가 승리할 수 있는 경우의 수가 있는 경우 '다른 플레이어'는 그 경우의 수를 둘 것이다. 그러면 더 늦게 끝나는 경우의 수를 택하면 된다.
• Achoice에 따라 '다른 플레이어'의 승패가 갈린다면, '현 플레이어'는 이기는 수 중 더 일찍 끝나는 수를 택하면 된다.

로 코드를 짜면 된다.

​

getMoveablePoints 함수는 현재 위치에서 이동 가능한 point들을 return하는 함수이다.

backtrack에서 종료 조건은 더 이상 움직이지 못할 때 다른 플레이어의 승이고 남은 턴 수는 0이므로 이를 리턴한다.

현재 플레이어가 이동할 수 있는 수들을 순회하면서 backtrack을 한다.

만약 backtrack 결과 '현 플레이어'가 승리할 수 있으면 '현 플레이어'는 그 수를 골라서 두면 되고, 만약 그 수들이 여러가지라면 더 빨리 끝나는 수를 택하면 된다.

backtrack 결과가 '현 플레이어'가 패배한다면 더 늦게 끝나는 수를 택하면 된다.

​

그리고 리턴 값은 {승리자, 남은 턴 수}를 리턴하면 된다. 독특한 문제였다.

 

// 사라지는 발판

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

using namespace std;

typedef pair<int, int> pii;

int max_r, max_c;
vector<vector<int>> boards;
vector<pii> players;

int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};

vector<pii> moves(10);

vector<pii> getMoveablePoints(pii cur_p){
    vector<pii> result;
    for(int i = 0; i<4; i++){
        pii next_p;
        next_p.first = cur_p.first + dr[i];
        next_p.second = cur_p.second + dc[i];
        if(0 <= next_p.first && next_p.first < max_r && 0 <= next_p.second && next_p.second < max_c && boards[next_p.first][next_p.second] == 1){
            result.push_back(next_p);
        }
    }
    return result;
}

// return .first : 승자, .second : 끝날 때 까지 남은 턴 수
pii backtrack(int isA){ // isA가 0이면 A, 1이면 B
    pii &player = players[isA]; // 현재 움직일 player
    pii player_backup = players[isA];
    
    vector<pii> moveable_points = getMoveablePoints(player);
    if(boards[player.first][player.second] == 0 || moveable_points.size() == 0){ // 못 움직이면 끝임.
        return {1 - isA, 0}; // 못 움직인다면 자신이 아닌 플레이어의 승. 남은 턴 수 == 0
    }
    
    
    int max_turn = -1, min_turn = 99999, canWin = -1; // canwin == 승리자
    for(pii mp : moveable_points){
        player = mp;
        boards[player_backup.first][player_backup.second] = 0;
        pii result = backtrack(1 - isA);
        int winner = result.first; // 0이면 A 승, 1이면 B 승
        int left_turn = result.second;
        player = player_backup;
        boards[player_backup.first][player_backup.second] = 1;
        
        // 핵심 로직
        if(winner == isA){ // 현 플레이어가 승리할 수 있으면
            canWin = isA; // 승리자는 현 플레이어
            min_turn = min(min_turn, left_turn); // 최대한 수를 짧게 가지고 간다.
        } else{
            if(canWin == isA) continue; // 승리할 수 있는 수가 있는데 패배하는 수를 고를 경우 continue
            canWin = 1 - isA; // 패배하는 경우의 수
            max_turn = max(max_turn, left_turn); // 최대한 길게 끌고 간다.
        }
    }

    return {canWin, (canWin == isA ? min_turn : max_turn) + 1};
}

int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
    max_r = board.size();
    max_c = board[0].size();
    boards = board;
    
    players.push_back({aloc[0], aloc[1]});
    players.push_back({bloc[0], bloc[1]}); // players[0] : A, 1 : B
    
    return backtrack(0).second;
}

 

3. 리틀 프렌즈 사천성

하... 문제 접근은 쉽게 했는데 너무 짜증난다. board를 전역변수로 사용했는데, 전역변수를 전부다 함수 parameter로 바꿔서 넣기만 했더니 통과했다. 다른 분들도 전역변수 초기화를 함수 내에서 하라는 말이 있는 것으로 보아, 전역변수를 사용하면 안 되는 문제인 것 같다. 알고리즘은 너무 쉽게 생각했는데...

먼저, '1번만 꺾일 수 있다'에서 많은 사람들이 dijkstra나 BFS 등 graph 탐색 알고리즘을 사용하는데, 1번만 꺾인다는 말은 ㄱ자 또는 ㄴ자로만 선을 이을 수 있다는 것이다. 따라서 ㄱ자 / ㄴ자 안에 다른 문자가 없는지 checkRow함수로 row를 check, checkCol 함수로 col을 check 한 수 canReach 함수로 from에서 to까지 도달 가능한지 검색한다.

이후에는, board에 대해 알파벳이 있는 경우 map의 key로, 해당 좌표는 map의 value vector에 push_back한다. 그러면 key가 오름차순 정렬된다.

이후 오름차순 알파벳에 해당하는 좌표 pair부터 검색 시작. 만약 못넣는다면 다음 것을 보고, 넣을 수 있다면 넣고 i=0으로 되돌린다. 이 결과, 모두가 visited이면 다 탐색한 것이고 그렇지 않다면 impossible인 것이다.

접근은 정말 쉬웠는데..

// 리틀 프렌즈 사천성

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

using namespace std;

typedef pair<int, int> pii;
typedef pair<pii, pii> ppiipii;

bool checkRow(int rfrom, int rto, int c, int cha, vector<string>& boards){
    int end = max(rfrom, rto), start = min(rfrom, rto);
    for(int r = start; r<=end; r++){
        if(boards[r][c] == cha || boards[r][c] == '.') continue;
        return false;
    }
    return true;
}

bool checkCol(int cfrom, int cto, int r, int cha, vector<string>& boards){
    int end = max(cfrom, cto), start = min(cfrom, cto);
    for(int c = start; c<=end; c++){
        if(boards[r][c] == cha || boards[r][c] == '.') continue;
        return false;
    }
    return true;
}

// c : 시작/도착 글자
// from/to : 출발/도착 좌표
bool canReach(pii from, pii to, char c, vector<string>& boards){
    if(checkRow(from.first, to.first, from.second, c, boards) && checkCol(from.second, to.second, to.first, c, boards)) return true;
    if(checkRow(from.first, to.first, to.second, c, boards) && checkCol(from.second, to.second, from.first, c, boards)) return true;
    return false;
}

string backtrack(int cur_depth, int max_depth, vector<vector<pii>>& word_coordinate, vector<bool>& visited, string cur_str, vector<string>& boards){
    string answer = "";
    if(cur_depth == max_depth && answer == "IMPOSSIBLE"){
        answer = cur_str;
        return answer;
    }
    
    for(int i = 0; i<word_coordinate.size(); i++){
        if(visited[i]) continue;
        pii from = word_coordinate[i][0];
        pii to = word_coordinate[i][1];
        char cur_char = boards[from.first][from.second];
        if(canReach(from, to, cur_char, boards)){
            visited[i] = true;
            boards[from.first][from.second] = '.';
            boards[to.first][to.second] = '.';
            answer += cur_char;
            i = -1;
        }
    }
    
    bool flag = true;
    for(bool b : visited){
        if(b == false) flag = false;
    }
    if(flag == false) answer = "IMPOSSIBLE";
    
    
    return answer;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
string solution(int m, int n, vector<string> board) {
    map<char, vector<pii>> mapper;
    for(int r = 0; r<m; r++){
        for(int c = 0; c<n; c++){
            if(board[r][c] == '*' || board[r][c] == '.') continue;
            mapper[board[r][c]].push_back({r, c});
        }
    }
    
    vector<vector<pii>> word_coordinate;
    for(auto [k, v] : mapper){
        word_coordinate.push_back(v);
    } // word_coordinate[i][0] : 첫 좌표, [1] : 두번째 좌표. word_coordinate는 오름차순 정렬.
    vector<bool> visited(word_coordinate.size(), false);
    
    return backtrack(0, word_coordinate.size(), word_coordinate, visited, "", board);
    
    
    
}

/*
경로가 1번 꺾여야 함은 어떻게 알까?
무조건 ㄱ 또는 ㄴ자가 되어야 한다. 그 경로에 다른 무언가가 있다면 없애지 못하는 것.
*/