260220 TIL - 챕터3 팀프로젝트 9일차

 

//행렬 회전 문제. 비슷한 문제가 몇번 나왔지만 이건 좀 다른 접근법이라 어려웠음.
//갈수록 문제에 수학이 많아지는데 너무 힘들다...

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int rotate(int x1, int y1, int x2, int y2, vector<vector<int>>& map)
{
    int minimum = 10001;
    int xtop = x1, ytop = y1, xbot = x2, ybot = y2;
    int backup = map[xtop][ytop];
    minimum = min(minimum, backup);
    
    for (int i = xtop; i < xbot; i++)
    {
        map[i][ytop] = map[i + 1][ytop];
        minimum = min(minimum, map[i + 1][ytop]);
    }
    for (int i = ytop; i < ybot; i++)
    {
        map[xbot][i] = map[xbot][i + 1];
        minimum = min(minimum, map[xbot][i + 1]);
    }
    for (int i = xbot; i > xtop; i--)
    {
        map[i][ybot] = map[i - 1][ybot];
        minimum = min(minimum, map[i - 1][ybot]);
    }
    for (int i = ybot; i > ytop; i--)
    {
        map[xtop][i] = map[xtop][i - 1];
        minimum = min(minimum, map[xtop][i - 1]);
    }
    map[xtop][ytop + 1] = backup;
    return minimum;
}

vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
    vector<int> answer;
    vector<vector<int>> map(rows, vector<int>(columns));
    
    int count = 1;
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < columns; j++)
        {
            map[i][j] = count;
            count++;
        }
    }
    for (const vector<int>& q : queries)
    {
        answer.push_back(rotate(q[0] - 1, q[1] - 1, q[2] - 1, q[3] - 1, map));
    }
    return answer;
}

//전력망을 둘로 나누기 문제. 처음으로 트리 라는 자료구조에 대해 알게되었고, DFS로 탐색하는 방식으로 해결함
//여전히 어렵긴 한데... 그래도 자료를 분석하는 방식에 대한 이해도는 조금 높아진 것 같음
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

void DFS(int start, int cut, int previous, int& count, const vector<vector<int>>& tree)
{
    count++;
    for (const int& i : tree[start])
    {
        if (i == cut || i == previous) continue;
        DFS(i, cut, start, count, tree);
    }
}

int solution(int n, vector<vector<int>> wires) {
    int answer = 101;
    vector<vector<int>> tree(n + 1);
    
    for(const vector<int>& w : wires)
    {
        int a = w[0];
        int b = w[1];
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    
    for (const vector<int>& w : wires)
    {
        int count = 0;
        DFS(w[0], w[1], 0, count, tree);
        answer = min(answer, abs(count - (n - count)));
    }
        
    return answer;
}

 

설 때문에 컨디션 복구를 못해서 팀프로젝트 관련 작업 조금 한거 말고는 거의 쉬다시피 했음... 주말 푹 쉬고 힘내서 하기로 함