백준: Class 5 - 12100, 16724

</br> 클래스 5 계속
</br>

12100: 2048 (Easy)

https://www.acmicpc.net/problem/12100

void up(){
    stack<int> st;
    for(int j = 0; j < n; j++){
        for(int i = n-1; i >= 0; i--){
            if( mmap[i][j] ) st.push(mmap[i][j]);
            mmap[i][j] = 0;
        }
        if( st.empty() ) continue;
        queue<int> q;
        int a = st.top();
        st.pop();
        while( st.size() ){
            int b = st.top();
            st.pop();
            if( a == b ){
                q.push(a*2);
                a = 0;
            }
            else{
                if( a ) q.push(a);
                a = b;
            }
        }
        if( a ) q.push(a);
        int i = 0;
        while( q.size() ){
            mmap[i++][j] = q.front();
            q.pop();
        }

    }
}

void down();
void lef()
void righ();

void func(int d){
    if( d == 5 ){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                ans = max(ans, mmap[i][j]);
            }
        }
        return;
    }

    vector< vector<int> > t = mmap;
    up();
    func(d+1);
    mmap = t;

    down();
    func(d+1);
    mmap = t;

    righ();
    func(d+1);
    mmap = t;

    lef();
    func(d+1);
    mmap = t;
}

문제에 게임 링크를 보자마자 홀린 듯이 했다 추억의 게임… 아직 실력은 죽지 않았다
아무튼, 구현 문제였다
각 방향으로 움직일 때, 그걸 스택에 쌓아 둔다.
그리고 꺼내면서, 결과를 큐에 넣는다.
그리고 큐를 팝하며 결과를 배열에 저장한다.

ex)
4
4 2 2 0
2 2 4 0
2 4 4 0
2 4 0 0

up()을 하면
j == 1
stack: 4 2 2 2
queue: 4 4 2

j == 2
stack: 2 2 4 4
queue: 4 4 4

j == 3
stack: 2 4 4
queue: 2 8

j == 4
stack:
queue:

따라서
4 4 2 0
4 8 8 0
2 0 0 0
0 0 0 0

down lef righ 함수는 up의 포문에서 i랑 j 증감이나 위치만 반대로 해 주면 되므로 생략한다
</br>

16724: 피리 부는 사나이

https://www.acmicpc.net/problem/16724

int mmap[1001][1001];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int ind[1000001];

struct UnionFind{
    vector<int> parent;
    UnionFind(int n) : parent(n){
        for(int i = 0; i < n; i++){
            parent[i] = i;
        }
    }
    int f(int u){
        if( u == parent[u] ) return u;
        return parent[u] = f(parent[u]);
    }
    void merg(int u, int v){
        u = f(u), v = f(v);
        if( u == v ) return;
        if( u < v ) swap(u, v);
        parent[u] = v;
    }
};

// in main()
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            char c;
            cin >> c;
            if( c == 'U' ) mmap[i][j] = 0;
            else if( c == 'D' ) mmap[i][j] = 1;
            else if( c == 'L' ) mmap[i][j] = 2;
            else if( c == 'R' ) mmap[i][j] = 3;
        }
    }

    UnionFind uf = UnionFind(n*m);

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            int nx = i + dx[mmap[i][j]];
            int ny = j + dy[mmap[i][j]];
            if( nx < 0 || n <= nx || ny < 0 || m <= ny ) continue;
            uf.merg(i*m+j, nx*m+ny);
        }
    }
    for(int i = 0; i < n*m; i++){
        uf.f(i);
    }

    int cnt = 0;
    for(int i = 0; i < n*m; i++){
        if( ind[uf.parent[i]] ) continue;
        ind[uf.parent[i]] = 1;
        cnt++;
    }
    cout << cnt << endl;

다행스럽게도 얘는 보자마자 union find라고 알겠더라
(i,j)에서 (nx,ny)로 이동한다면, (i,j)와 (nx,ny)를 병합하고 그 기준은 작은 번호를 부모로 했다(따라서 랭크가 필요 없음).
마지막에 업데이트 된 parent 배열에서, 다른 부모들의 수를 세 주면 된다.

ex) 백준 예제
3 4
DLLL
DRLU
RRRU

초기 parent는 자기 자신
 0  1  2  3
 4  5  6  7
 8  9 10 11

(0,0)은 D므로 낮은 번호 기준으로 합침
 [0]  1  2  3
 [0]  5  6  7
  8   9 10 11

(0,1)은 L이므로 낮은 번호 기준으로 합침
 [0]  [0]  2  3
  0    5   6  7
  8    9  10 11

...

 0  0  0  0
 0  5  5  0
 0  0  0  0
ans = 2

참고로, 마지막에 parent 배열이 업데이트가 안 되었을 수도 있어서

    for(int i = 0; i < n*m; i++){
        uf.f(i);
    }

이거 한 번 넣어서 다 업데이트해 주고 답을 세면 된다.
</br>

---

오늘은 8월 22일
월요일인 내일부터 Swift로 ios 개발 수업을 듣기로 했다 그래서 문제 풀이는 많이는 못하겠네
그래도 어차피 포스트는 밀려 있긴 하다 이 포스트는 9월 넘어서 올라갈 것 같다
</br>