프로그래밍

https://programmers.co.kr/learn/courses/30/lessons/72414

[난이도] level3
[유형] 부분합

[풀이]
시간의 최대 길이가 N:100*60*60 정도에 logs의 크기가 M:300000 이므로
O(N*M) 알고리즘으로는 시간내에 해결이 불가능 합니다.
O(N) 혹은 O(M) 알고리즘을 생각해봐야 합니다.
NlogN을 생각하려면 정렬, 이분탐색 , set 등과 연관이 있어야 하는데 연관도가 떨어져 보입니다.

cnt[i] = 0~i까지 재생했을 때 총 누적 재생시간 (0<= i <= 나올 수 있는 최대 시간) 을 저장하는
cnt 배열을 만듦으로써 O(N+M)의 답을 구할 수 있습니다.

1)
일단 logs의 string을 초로 변환하여 start,end 타임을 구합니다.
sscanf(str.c_str(),"%d:%d:%d",&h,&m,&s) 와 같이 sscanf를 쓰면
형식이 정해진 string에서 필요한 정보를 쉽게 추출할 수 있습니다.

2)
구한 start,end를 이용해 cnt[start+1]++, cnt[end+1]-- 연산을 해주어
start와 end 지점에서 한 시청자의 재생이 시작,종료 되었음을 기록합니다.
+1을 해주는 이유는 start에서 재생이 시작 되었다면 start+1이 되서야 1초가 경과한 것이기 때문입니다.
마찬가지로 end일때도 end에 종료되면 end+1부터 종료가 된것이 영향이 있기 때문입니다.

3)
cnt[i]를 이용해 cnt[i]를 i초에 몇명의 시청자가 재생중인지를 기록하도록 할 것입니다.
for(int i=1;i<=pt;i++) cnt[i]+=cnt[i-1] 와 같이 누적합을 구해주면 됩니다.

4)
한번 더 위와 3)과 같이 누적해주면 cnt[i] = 0~i까지 재생했을 때 총 누적 재생시간 이 됩니다.
0~i까지 누적해서 더하기 때문에 위의 결과가 저장되는 것입니다.

5)
이제 어느 구간이 가장 누적 재생시간이 많이 나오는 지를 구해야 합니다.
cnt[i]-cnt[i-at] (at:adv_time <= i <= pt:play_time) 중 최댓값을 구하면서 그때의 i-at (시작 시간)을 구해줍니다.
이 값을 HH:MM:SS 형식으로 변환해주면 됩니다.

#include <string>
#include <vector>
using namespace std;
using ll = long long;
int pt,at;
ll cnt[400000];
int convert(string str){
    int h,m,s;
    sscanf(str.c_str(),"%d:%d:%d",&h,&m,&s);
    return h*3600+m*60+s;
}
string solution(string play_time, string adv_time, vector<string> logs) {

    pt=convert(play_time);
    at=convert(adv_time);

    vector<pair<int,int>> v;
    for(auto s : logs){
        int idx=s.find("-");
        int start=convert(s.substr(0,idx)), end=convert(s.substr(idx+1));
        cnt[start+1]++;
        cnt[end+1]--;
    }
    for(int j=0;j<2;j++)
        for(int i=1;i<=pt;i++) 
            cnt[i]+=cnt[i-1];

    ll mv=0;
    int t=0;
    for(int i=at;i<=pt;i++){
        if(mv<cnt[i]-cnt[i-at]){
            mv = cnt[i]-cnt[i-at];
            t=i-at;
        }
    }
    string rh=to_string(t/3600); 
    string rm=to_string((t%3600)/60);
    string rs=to_string((t%60));
    if(rh.size()<2) rh='0'+rh;
    if(rm.size()<2) rm='0'+rm;
    if(rs.size()<2) rs='0'+rs;
    string ret = rh+":"+rm+":"+rs;
    return ret;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/광고_삽입.cpp

https://programmers.co.kr/learn/courses/30/lessons/77886

[난이도] level3
[유형] Greedy

[풀이]

나올 수 있는 모든 110을 뽑아서 남은 문자열에서 가장 뒤에 있는 0 뒤에 모든 110을 붙혀주면 되는 문제입니다.

이게 가능한 이유는 문자열에 있는 존재하는 모든 110을 제거했다면,
1이 연속으로 2개 이상 나오는 경우는 "111111"과 같이 0이 존재하지 않는 경우밖에 없습니다.
왜냐하면 0이 붙는 순간 "110"이 되어 제거되기 때문입니다.

결국 남은 문자열은
1만 남은 경우 또는 "1001010"과 같이 1 다음에는 무조건 0이 나오는 형태 두가지 경우일 수밖에 없습니다.

1만 남은 경우에는 사전순으로 작은 문자가 되려면
110들을 문자열의 앞에다가 붙혀야 합니다. ex) "110110+11111"

1과 0이 같이 나오는 "10010100" 같은 경우에는
11이 연속으로 나오는 "110"을 무조건 맨 마지막 0 뒤에 넣어야 합니다.
앞쪽에 넣게 되면 연속된 "11"에 의해 사전순으로 뒤로 밀리게 되기 때문입니다.

위 두가지 케이스를 한번에 처리하기 위해 0을 남은 문자열 앞에 더해주었습니다.
이러면 마지막 0의 위치만 찾아서 제거한 "110"들을 넣기만 하면 됩니다.

#include <string>
#include <vector>
using namespace std;
string sol(string str){
    string ret,ans;
    int cnt=0;
    for(auto c : str){
        if(c=='0' && ret.size()>=2 && ret.substr(ret.size()-2,2)=="11"){            
            ret.pop_back();ret.pop_back();
            cnt++;
        } else ret.push_back(c);
    }
    ret='0'+ret;
    int idx;
    for(int i=ret.size()-1;i>=0;i--){
        if(ret[i]=='0') {
            idx=i;
            break;
        }
    }
    for(int i=0;i<=idx;i++) ans+=ret[i]; 
    while(cnt--) ans+="110";
    for(int i=idx+1;i<ret.size();i++) ans+=ret[i];
    return ans.substr(1);
}
vector<string> solution(vector<string> s) {
    vector<string> answer;
    for(auto str : s) answer.push_back(sol(str));
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/110_옮기기.cpp

https://programmers.co.kr/learn/courses/30/lessons/70130

[난이도] level3
[유형] Greedy

[풀이]
a배열의 최대 길이가 50만이기 때문에 한번 배열을 스캔하면서 최대 길이의 스타수열을 찾아야합니다.

"a의 모든 수는 0 이상 (a의 길이) 미만입니다."
위의 조건에 의해 나올 수 있는 수도 50만 미만이기 때문에 두개의 배열을 이용해 문제를 풀 수 있습니다.
cnt[500000],idx[500000] 두 배열을 선언하여

cnt[k] : 현재까지 확인된 숫자 k를 교집합으로 포함하는 스타 수열의 최대길이
idx[k] : 현재까지 확인된 숫자 k를 교집합으로 포함하는 스타 수열의 마지막 index

위와 같은 값을 저장하는 용도로 사용합니다.

이제 a배열을 0부터 순회하면서
i번째 원소를 확인중일 때, 조건을 만족한다면 cnt[a[i]], idx[a[i]]를 업데이트 할 수 있습니다.

i번째 원소의 왼쪽에 짝이 있는 경우와, 오른쪽에 짝이 있는 경우가 있을 수 있습니다.

왼쪽에 짝이 있으려면,
idx[a[i]] 즉, a[i]를 교집합으로 하는 스타 수열의 마지막 index보다는 i-1이 작아야하며 (idx[a[i]] < i-1)
a[i] != a[i-1]을 만족해야 합니다. (서로 값이 달라야 하기 때문에)

i-1만 검사해도 되는 이유는 만약 a[i] == a[i-1] 이고 a[i-1] != a[i-2] 라면 (예를 들어 a[i]가 1일때 [...2,1,1] 이런 형태)
idx[a[i]]가 i-1일 것이므로 idx[a[i]] < i-1 에서부터 조건을 만족하지 못하여 a[i] != a[i-1]는 검사할 필요가 없어집니다.

왼쪽에 짝이 있다면 i가 이제 마지막 index가 되므로 idx[a[i]]=i로 업데이트 해주고
짝이 한개 추가되었기 때문에 cnt[a[i]]++를 해주고 다음 index를 검사합니다.

만약 왼쪽에 짝이 없다면 오른쪽에 있는지 검사해야 합니다.
오른쪽에 a[j] != a[i] 를 만족하는 j가 있다면 idx[a[i]]=j 로 업데이트 해주면 됩니다.

for문을 돌때마다
먼저 if(i<=idx[a[i]]) continue 를 추가해줍니다.
위 조건에 걸렸다는 것은 스타 수열의 index가 i 뒤에 있다는 것이기 때문에 i는 스타 수열에 포함될 수 없어 검사할 필요가 없습니다.

최종적으로 cnt[i] (0<=i<(a의 길이)) 중에 최댓값을 구하고, 쌍의 개수이므로 그 값에 2배를 해주면 됩니다.

알고리즘 분류가 애매하지만 매 루프마다 최적의 index를 고르는 것이기 때문에 Greedy 문제로 생각됩니다.

#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
const int mxN=5e5;
int cnt[mxN],idx[mxN],ans;
int solution(std::vector<int> a) {
    memset(idx,-1,sizeof(idx));
    for(int i=0;i<a.size();i++){
        if(i<=idx[a[i]]) continue;
        if(i>0&& idx[a[i]] < i-1 && a[i]!=a[i-1]){
            cnt[a[i]]++, idx[a[i]]=i;
            continue;
        }
        int j=i;
        while(++j<a.size() && a[j] == a[i]);
        if(j<a.size()) cnt[a[i]]++, idx[a[i]]=j;
    }
    for(int i=0;i<a.size();i++) ans=std::max(ans,cnt[i]);
    return ans*2;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/스타_수열.cpp

https://programmers.co.kr/learn/courses/30/lessons/84021

[난이도] level3
[유형] 브루트포스

[풀이]
board의 빈곳의 모양과, table의 조각의 모양을 각각 2차원 vector에 저장한 뒤 매칭시켜서 몇개나 매칭이 될 수 있는지 구하면 됩니다.
각 모양을 구할 때는 dfs를 이용하여 모양의 좌표들을 저장해주면서 상,하,좌,우 끝값의 좌표를 기록해줍니다.
이것을 알아야 모양의 행과 열과의 길이를 알 수 있고, 올바른 크기의 2차원 vector를 선언하여 좌표를 저장할 수 있습니다.
board 또는 table 중 한쪽의 모양들은 시계방향으로 회전시키며 4방향에 대한 모양을 따로 저장해야 합니다.
아래 코드에서는 vector<vvi> shapes[4],shapes_tb 를 선언하여 shapes에는 빈칸 모양의 4방향 vector를, shapes_tb에는 table의 조각 모양 vector를 저장하였습니다.
4방향을 구할 때는 시계방향으로 90도 돌린 vector를 반환하는 함수를 한개만 선언하면 연속적으로 돌려주면서 4방향을 모두 구할 수 있습니다.

시간 복잡도는 최악의 경우 O((4*50*50)*(50*50)) 정도 나오는것으로 보여 시간내에 AC를 받는 것이 가능합니다.

#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
using vvi=vector<vector<int>>;
const int dy[4]={-1,1,0,0}, dx[4]={0,0,1,-1}, inf = 9e8;
vector<vvi> shapes[4],shapes_tb;
bool visit[50][50];
int N,l,r,u,d,scnt,ans;
vector<pair<int,int>> p;
void init(){
    u=l=inf;
    d=r=-inf;
    p.clear();    
}
vvi rotate(vvi& org){
    int r = org[0].size();
    int c = org.size();
    vvi ret = vvi(r,vector<int>(c));

    for(int i=0;i<r;i++)
        for(int j=0;j<c;j++)
            ret[i][j]=org[c-j-1][i];

    return ret;
}
void dfs(int y,int x,int k,vvi& b){
    visit[y][x]=1;
    p.push_back({y,x});
    l=min(l,x),r=max(r,x);
    u=min(u,y),d=max(d,y);

    for(int i=0;i<4;i++){
        int ny=y+dy[i],  nx=x+dx[i];
        if(ny<0||nx<0||ny>=N||nx>=N||b[ny][nx]!=k||visit[ny][nx]) continue;
        dfs(ny,nx,k,b);
    }
}
int match(vvi& a,vvi& b){
    if(a.size()!=b.size() || a[0].size() != b[0].size()) return -1;
    int ret=0;
    for(int i=0;i<a.size();i++)
        for(int j=0;j<a[0].size();j++){
            if(a[i][j]+b[i][j]!=1) return -1; 
            ret+=a[i][j];
        }
    return ret;
}
int solution(vvi board,vvi table) {

    N=board.size();
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(!board[i][j] && !visit[i][j]){
                init();
                dfs(i,j,0,board);
                int row = d-u+1, col = r-l+1;
                vvi shape = vvi(row,vector<int>(col,1));
                for(auto& v : p) shape[v.first-u][v.second-l]=0;

                for(int k=0;k<4;k++){
                    shapes[k].push_back(shape);
                    shape=rotate(shape);
                }
            }
        }
    }
    memset(visit,0,sizeof(visit));
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(table[i][j] && !visit[i][j]){
                init();
                dfs(i,j,1,table);
                int row = d-u+1, col = r-l+1;
                vvi shape = vvi(row,vector<int>(col,0));
                for(auto& v : p) shape[v.first-u][v.second-l]=1;
                shapes_tb.push_back(shape);
            }
        }
    }
    vector<bool> filled(shapes[0].size());
    for(auto stb : shapes_tb){
        for(int i=0;i<shapes[0].size();i++){
            if(filled[i]) continue;
            bool ok=false;
            for(int j=0;j<4;j++){
                int ret = match(stb,shapes[j][i]);
                if(ret!=-1){
                    ok=true;
                    ans+=ret;
                    filled[i]=true;
                    break;
                }
            }
            if(ok) break;
        }
    }
    return ans;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/위클리_챌린지_3주차.cpp

https://programmers.co.kr/learn/courses/30/lessons/81303

[난이도] level3
[유형] set

[풀이]
행의 최대 수가 100만이기 때문에 단순히 vector를 이용하면 삽입,삭제시 비용이 많이 들기 때문에
다른 자료구조를 이용해야 합니다. 물론 커서를 움직일 때는 배열의 경우 특정 index에 O(1)로 접근이 가능하기 때문에
유리하지만 문제 조건에서 모든 cmd의 커서를 움직이는 총 횟수의 합이 1000000 이하이기 때문에 삽입/삭제 연산을 효율적으로
하는 것이 더 중요합니다.

vector는 특정한 위치에 삽입,삭제시 그곳을 기준으로 모든 원소를 움직여 빈공간이 생기지 않도록 하기 때문에 삽입/삭제시 불리합니다.

그렇다고 stl list를 이용하면 복구 연산시 복구 되어야할 위치를 찾기가 어렵습니다.

그래서 set을 이용하였습니다. set은 balanced tree 형태로 되어있어 O(logN)으로 삽입/삭제가 가능하기 때문입니다.
커서의 이동도 iterator를 유지하면 위,아래로 자유롭게 할 수 있습니다.

삭제시에는 set에서 현재 iterator 위치의 원소를 삭제하고, 그 원소를 stack에 넣어주고 복원시에 꺼내서 set에 insert 해주기만 하면
자동으로 복구가 됩니다.
주의할 점이 삭제시 반환된 iterator가 end()인 경우(마지막 원소를 삭제한 경우) iterator를 한 칸 앞으로 (-- 연산) 옮겨주어야 합니다.
왜냐하면 end()는 마지막 원소의 한 칸 뒤를 가르키기 때문에 커서를 위로 올리는 연산시 (-- 연산) 한칸 덜 올라가게 되기 때문입니다.

#include <string>
#include <vector>
#include <set>
#include <stack>
using namespace std;
stack<int> st;
set<int> a;
string solution(int n, int k, vector<string> cmd) {
    string ans;
    for(int i=0;i<n;i++) {
        a.insert(i);
        ans+='X';
    }
    auto it = a.begin();
    while(k--) it++; 
    for(auto c : cmd){
        char q = c[0];
        int num;
        if(c.size()>1) num = stoi(c.substr(2));

        if(q=='U') while(num--) it--;
        else if(q=='D') while(num--) it++;
        else if(q=='Z') {
            a.insert(st.top()); st.pop();
        }
        else {
            st.push(*it);
            it = a.erase(it);
            if(it==a.end()) it--;
        }
    }
    for(auto v : a) ans[v]='O';
    return ans;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/표_편집.cpp

https://programmers.co.kr/learn/courses/30/lessons/12971

[난이도] level3
[유형] DP

[풀이]
첫번째 스티커를 떼면 마지막 N번째 스티커는 절대로 뗄 수 없고,
첫번째 스티커를 떼지 않으면 마지막 N-1번째 스티커에 따라 뗄 수 있을수도 없을수도 있습니다.

이를 이용해 첫번째 스티커를 뗀 경우와 안뗀 경우를 나눠서 생각하면 편합니다.

dp[n][f] 배열에서 f가 0이면 첫번째 스티커를 뗀 경우, 1이면 떼지 않은 경우로 생각하여 문제를 풉니다.

dp[n][f] (sol(n,f)) 의 의미는 n~N-1까지만 고하고, n번째 스티커는 뗄수도 있을 때, 얻을 수 있는 최댓값입니다.

top-down으로 진행했을 때 점화식은 아래와 같습니다.
sol(n,f) = max(sticker[n]+sol(n+2,f),sol(n+1,f))

sticker[n]+sol(n+2,f) : n번째 스티커를 뗐을 때입니다. n번 스티커의 수에 n+1번째 스티커는 뗄 수 없으므로 sol(n+2,f)를 더해줍니다.
sol(n+1,f) : n번째 스티커를 떼지 않았을 때이므로 1 건너뛰어 sol(n+2,f) 입니다.

마지막으로 n이 N-1이 되었을 때, f가 1이면 N-1번 스티커는 떼지 못하므로 0을 return, 0이면 뗄 수 있으므로 sticker[N-1]를 return 해줍니다.

#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int N,dp[100002][2];
vector<int> sticker;
int sol(int n,int f){
    if(n>=N) return 0;
    if(n==N-1) return f ? 0 : sticker[N-1];
    int& ret = dp[n][f];
    if(ret!=-1) return ret;
    ret=max(sticker[n]+sol(n+2,f),sol(n+1,f));
    return ret;
}
int solution(vector<int> _sticker)
{
    sticker=_sticker;
    N=sticker.size();
    memset(dp,-1,sizeof(dp));
    return max(sol(1,0),sol(2,1)+sticker[0]);
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/스티커_모으기(2).cpp

https://programmers.co.kr/learn/courses/30/lessons/72415

[난이도] level3
[유형] 브루트포스

[풀이]
브루트포스+BFS를 이용한 거리찾기가 결합된 복잡한 구현 문제입니다.
보드가 4x4이고, 나올수 있는 카드의 쌍이 최대 6개라는점을 보고 브루트포스라는 것을 의심해야 합니다.
4x4 맵의 경우 어지간한 문제는 무식하게 풀어도 시간내에 해결이 가능합니다.

이미 카드의 앞면을 알고 있기 때문에 조작 횟수를 최소로 하려면 쓸데없는 칸에 방문하지 않고
카드쌍을 바로바로 제거할 수 있도록 방문해야 합니다.
예를 들어 [1-1/1-2],[2-1/2-2],[3-1/3-2] 총 3쌍의 카드가 있을 때
1-1 -> 1-2 -> 2-2 -> 2-1 -> 3-1 -> 3-2 이런식으로 이동해야 효율적이며
1-1 -> 2-1 -> 1-2 .. 이런식으로 1번카드 갔다가 2번 카드갔다가 하면 불필요한 조작이 늘어납니다.

하지만 어떤 카드부터 지워야 할지는 알수 없기 때문에 모든 경우를 다해봐야 합니다.
next_permutation으로 모든 순서를 구할 수 있습니다.
여기서는 seq vector에 모든 카드 종류를 넣고 순열을 구하였습니다.

하지만 여기서 또 정해야 할것이 1->2->3 순서로 카드를 없애는 경우에서도
1-1 -> 1-2 순서로 방문해서 1을 없애는 경우, 1-2 -> 1-1 순서로 방문해서 1을 없애는 경우가
다른 경우입니다. 2와 3을 방문할때도 같은 종류의 두가지 카드중 어떤 것을 방문할지를 정해야 합니다.

위 과정은 sol(int n) 재귀함수를 통해 백트래킹으로 진행하였습니다.
입력을 받을 때, vector<pair<int,int>> table[7]를 이용해 table[카드 종류]에 같은 종류의 두개의 카드 좌표를 저장해두었습니다.

이를 이용해 vector<pair<int,int>> mseq 에
1->2->3 순서로 카드를 없애는 케이스에서는

(1-1의 좌표),(1-2의 좌표),(2-1의 좌표),(2-2의 좌표),(3-1의 좌표),(3-2의 좌표)
(1-1의 좌표),(1-2의 좌표),(2-1의 좌표),(2-2의 좌표),(3-2의 좌표),(3-1의 좌표)
(1-1의 좌표),(1-2의 좌표),(2-2의 좌표),(2-1의 좌표),(3-1의 좌표),(3-2의 좌표)
...
...
와 같이 모든 케이스가

n==total(카드 종류의 개수) 이 될때 저장되게 됩니다.

이제 시작점 (r,c)를 시작으로 mseq에 저장된 좌표를 순서대로 방문하기만 하면 됩니다.
이제 순서가 정해졌기 때문에 카드의 종류 등은 생각할 필요가 없습니다.
위의 모든 케이스에서 조작 횟수를 구한 후 그것들중에 최솟값을 구하면 됩니다.

bfs(int fy,int fx,int ty,int tx) 함수를 통해 (fy,fx)에서 (ty,tx)로 갈때
드는 최소 조작 횟수를 구해주었습니다. end 함수는 ctrl+방향키 조작했을 때 도착하는
좌표를 구해주는 함수입니다.

mseq의 좌표를 순서대로 방문하면서 카드가 제거되는 순간 board에서 그 좌표의 값은 0으로
만들어 주어야 합니다. 그래서 매 시행마다 board를 복사해서 사용하였습니다.
제거되는 순간은 mseq의 index가 홀수인 순간입니다.
이유는 0,1,2,3,4,5 일때
1을 방문한 순간 0,1(1번카드)
3을 방문한 순간 2,3(2번카드)
5를 방문한 순간 4,5(3번카드)
가 각각 지워지기 때문입니다. 이 때 지워주지 않으면 ctrl+방향 조작시 지워져야 했던 카드에 막혀
올바르지 않은 곳으로 위치할 수 있습니다.

위 과정으로 구한 최솟값에 Enter 연산인 (카드의 종류*2) 를 더해준 것이 최종 정답입니다.

시험시간에 풀었다면 시간내에 풀지 못햇을 것 같은 복잡한 문제입니다.
최대한 과정을 쪼개서 간단한 문제로 만드는 것이 중요한 것 같습니다.

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <cstring>
#include <queue>
using namespace std;
int total,ans=987654321;
int dy[4]={0,0,1,-1};
int dx[4]={1,-1,0,0};
int R,C;
bool visit[4][4];
vector<pair<int,int>> table[7];
vector<int> seq;
vector<pair<int,int>> mseq;
vector<vector<int>> org_board,board;
bool inRagne(int y,int x){
    return y>=0&&x>=0&&y<4&&x<4;
}
pair<int,int> end(int y,int x,int k){
    while(1){
        y+=dy[k]; x+=dx[k];
        if(!inRagne(y,x)){
            y-=dy[k], x-=dx[k];
            break;
        }
        if(board[y][x]>0) break;
    }
    return {y,x};
}
int bfs(int fy,int fx,int ty,int tx){
    memset(visit,0,sizeof(visit));
    queue<pair<int,int>> q;
    visit[fy][fx]=1;
    q.push({fy,fx});
    int ret=0;
    while(!q.empty()){
        int sz = q.size();
        while(sz--){
            auto [y,x] = q.front(); q.pop();
            if(y==ty&&x==tx) return ret;
            for(int i=0;i<4;i++){
                int ny=y+dy[i],nx=x+dx[i];
                if(!inRagne(ny,nx)) continue;
                if(!visit[ny][nx]){
                    q.push({ny,nx});
                    visit[ny][nx]=1;
                }
                auto [ky,kx] = end(y,x,i);
                if(!visit[ky][kx]){
                    q.push({ky,kx});
                    visit[ky][kx]=1;
                }
            }
        }
        ret++;
    }
    return -1;
}
void sol(int n){
    if(n==total){
        board = org_board;
        int cy=R,cx=C,res=0;
        for(int i=0;i<mseq.size();i++){
            auto [ny,nx] = mseq[i];
            res+=bfs(cy,cx,ny,nx);
            if(i&1) board[ny][nx]=board[cy][cx]=0;
            cy=ny,cx=nx;
        }
        ans=min(ans,res);
        return;
    }
    int cur = seq[n];
    mseq.push_back(table[cur][0]); mseq.push_back(table[cur][1]);
    sol(n+1);
    mseq.pop_back(); mseq.pop_back();

    mseq.push_back(table[cur][1]); mseq.push_back(table[cur][0]);
    sol(n+1);
    mseq.pop_back(); mseq.pop_back();
}
int solution(vector<vector<int>> board, int r, int c) {
    R=r, C=c;
    org_board = board;
    set<int> st;
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++) {
            if(board[i][j]>0) {
                st.insert(board[i][j]);
                table[board[i][j]].push_back({i,j});
            }
        }
    total = st.size();
    for(auto v : st) seq.push_back(v);
    do{
        sol(0);
    }while(next_permutation(seq.begin(),seq.end()));
    return ans+st.size()*2;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/카드_짝_맞추기.cpp

https://programmers.co.kr/learn/courses/30/lessons/76503

[난이도] level3
[유형] DFS

[풀이]
트리의 리프노드에서부터 자신을 0으로 만들고, 나머지를 부모 노드로 전달했을 때,
최종으로 값을 전달받는 루트노드가 0이 된다면 조건을 만족하는 것입니다.
DFS를 통해 리프부터 값을 누적해갈 수 있으며 각 노드의 return 이전에 연산 횟수를 더해주면 됩니다.

import java.util.*
import kotlin.math.abs
const val mxN = 300000
var adj = Array(mxN){ mutableListOf<Int>()}
var b = LongArray(mxN)
var ans=0L
fun dfs(par:Int,n:Int):Long{
    var ret = b[n]
    for(i in 0..adj[n].size-1){
        if(adj[n][i]!=par) ret+=dfs(n,adj[n][i])
    }
    ans+=abs(ret)
    return ret
}
class Solution {
    fun solution(a: IntArray, edges: Array<IntArray>): Long {
        for(i in a.indices) b[i]=a[i].toLong()
        for((u,v) in edges){
            adj[u].add(v)
            adj[v].add(u)
        }
        if(dfs(-1,0)!=0L) ans=-1
        return ans
    }
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/모두_0으로_만들기.cpp