백준: Class 5 - 16946, 17143

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

16946: 벽 부수고 이동하기 4

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

void bfs(int ii, int jj, int d){
    queue< pair<int, int> > q;
    q.push(make_pair(ii, jj));

    zerogroups[ii][jj] = d;
    zeroarr[d]++;
    while( q.size() ){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if( nx < 0 || n <= nx || ny < 0 || m <= ny ) continue;
            if( mmap[nx][ny] == 0 && zerogroups[nx][ny] == 0 ){
                q.push(make_pair(nx, ny));
                zerogroups[nx][ny] = d;
                zeroarr[d]++;
            }
        }
    }
}

// in main()
    int d = 1;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if( mmap[i][j] == 0 && zerogroups[i][j] == 0 ){
                bfs(i, j, d);
                d++;
            }
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if( mmap[i][j] == 1 ){
                set<int> st;
                for(int k = 0; k < 4; k++){
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if( nx < 0 || n <= nx || ny < 0 || m <= ny ) continue;
                    if( zerogroups[nx][ny] ) st.insert(zerogroups[nx][ny]);
                }
                for(int a : st){
                    mmap[i][j] += zeroarr[a];
                }
                mmap[i][j] %= 10;
            }
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cout << mmap[i][j];
        }
        cout << '\n';
    }

정신이 나갔다 계속 뭐지 뭐지 하면서 고쳤는데 출력 할 때 한 칸씩 띄워서 4번 틀렸다
얜 좀 쉬운 편인데…ㅜㅜ 최대한 시간을 줄이기 위해서, 일단 붙어 있는 0들을 다 확인한다.

ex) 백준 예제 2
4 5
11001
00111
01010
10101

bfs 탐색 후 zerogroups
0 0 1 1 0
2 2 0 0 0
2 0 3 0 4
0 5 0 6 0

zeroarr: 0 2 3 1 1 1 1
(1번 그룹 2개, 2번 그룹 3개...)

그리고 1들의 주변 4칸을 탐색한다. 중복을 방지하기 위해 set에 넣어준다.
다 더하고, 10으로 나눠주면 됨
</br>

17143: 낚시왕

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

void sharkmove(int shark){
    int x = rr[shark];
    int y = cc[shark];
    int d = dd[shark];
    for(int i = 0; i < ss[shark]; i++){
        x += dx[d];
        y += dy[d];
        if( x < 0 || r <= x || y < 0 || c <= y ){
            x -= 2*dx[d];
            y -= 2*dy[d];
            if( d == 1 ) d = 2;
            else if( d == 2 ) d = 1;
            else if( d == 3 ) d = 4;
            else if( d == 4 ) d = 3;
        }
    }
    rr[shark] = x;
    cc[shark] = y;
    dd[shark] = d;
    if( t[x][y] ){
        if( zz[t[x][y]] < zz[shark] ){
            catched[t[x][y]] = 1;
            t[x][y] = shark;
        }
        else catched[shark] = 1;
    }
    else t[x][y] = shark;
}

void func(){
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            t[i][j] = 0;
        }
    }
    for(int i = 1; i <= m; i++){
        if( catched[i] ) continue;
        sharkmove(i);
    }
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            mmap[i][j] = t[i][j];
        }
    }
}

// in main()
    for(int i = 1; i <= m; i++){
        cin >> rr[i] >> cc[i] >> ss[i] >> dd[i] >> zz[i];
        rr[i]--; cc[i]--;
        if( dd[i] <= 2 ) ss[i] %= 2*(r-1);
        else ss[i] %= 2*(c-1);
    }
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            mmap[i][j] = 0;
        }
    }
    for(int i = 1; i <= m; i++){
        mmap[rr[i]][cc[i]] = i;
    }
    int ans = 0;
    for(int j = 0; j < c; j++){
        for(int i = 0; i < r; i++){
            if( mmap[i][j] ){
                catched[mmap[i][j]] = 1;
                ans += zz[mmap[i][j]];
                mmap[i][j] = 0;
                break;
            }
        }
        func();
    }
    cout << ans << endl;

삼성 SW 역량 테스트 문제라는데 이건 몇 분만에 풀어야 했던 걸까…
아무튼 속도가 1000까지인데, 상어 이동을 그냥 1씩 다 하면 백 퍼 시간초과 날 거 같아서 생각해 봤는데, 직접 이동 몇 번 해 보니까 세로 방향이면 %= 2*(r-1), 가로 방향이면 %= 2*(c-1)를 하면 되겠더라. 그 다음은 낚시하고, 상어 움직이고 하면 되는데, 주의할 점은 상어가 상어 먹을 때 업데이트를 잘 해줘야 한다
</br>

---

맑은 머리로 풉시다
</br>