백준: Class 4 - 2096, 2206, 2638

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

2096: 내려가기

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

    for(int i = 0; i < n; i++){
        cin >> nums[i][0] >> nums[i][1] >> nums[i][2];
    }

    int a = nums[0][0], b = nums[0][1], c = nums[0][2];
    int am = nums[0][0], bm = nums[0][1], cm = nums[0][2];
    for(int i = 1; i < n; i++){
        int aa, bb, cc;
        aa = nums[i][0] + max(a, b);
        bb = nums[i][1] + max({a, b, c});
        cc = nums[i][2] + max(b, c);
        a = aa; b = bb; c = cc;

        aa = nums[i][0] + min(am, bm);
        bb = nums[i][1] + min({am, bm, cm});
        cc = nums[i][2] + min(bm, cm);
        am = aa; bm = bb; cm = cc;
    }

    cout << max({a, b, c}) << ' ';
    cout << min({am, bm, cm}) << '\n';

메모리 제한 4MB에 시간 제한 1초면 플렉스하며 코딩은 못하겠네
4MB면 인트 100만 개 정도다 근데 n이 10만이면 크게 상관있나?
아무튼 가난하게 짜 보면 dp 테이블 만드는 건 공간 사치니까 그냥 현재 열 별 최대 점수를 저장하는 정수만 3개 선언하자
이왕 포문 돌리는 거 최대랑 최소도 같이 구하자
쉬운데 골드 4라니 좋구나
</br>

2206: 벽 부수고 이동하기

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

    queue<P> q;
    P p = {0, 0, 1, 1};
    q.push(p);
    visited[1][0][0] = 1;
    int ans = -1;
    while( q.size() ){
        int x = q.front().x;
        int y = q.front().y;
        int w = q.front().w;
        int d = q.front().d;
        q.pop();
        if( x == n-1 && y == m-1 ){
            ans = d;
            break;
        }
        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] == 1 ){
                if( w && visited[0][nx][ny] == 0 ){
                    P p = {nx, ny, 0, d+1};
                    q.push(p);
                    visited[0][nx][ny] = 1;
                }
            }
            else if( visited[w][nx][ny] == 0 ){
                P p = {nx, ny, w, d+1};
                q.push(p);
                visited[w][nx][ny] = 1;
            }
        }
    }
    cout << ans << endl;

나는 bfs가 좋아
위치 x, 위치 y, 벽 w, 거리 d를 묶어서 큐에 저장한다
visited[] 배열은 현재 벽을 부술 수 있는 지, 아닌 지로 구분해서 int visited[2][1001][1001];로 선언했다.
만약 1인데 지금 기회가 있으면 부수고 아님 말고 하게 하면 된다
</br>

2638: 치즈

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

void isOut(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            outside[i][j] = 0;
        }
    }
    queue< pair<int, int> > q;
    q.push(make_pair(0, 0));
    outside[0][0] = 1;
    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( cheese[nx][ny] == 0 && outside[nx][ny] == 0 ){
                q.push(make_pair(nx, ny));
                outside[nx][ny] = 1;
            }
        }
    }
}

bool func(){
    isOut();
    stack< pair<int, int> > st;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if( cheese[i][j] == 0 ) continue;
            int cnt = 0;
            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( cheese[nx][ny] == 0 && outside[nx][ny] == 1 ) cnt++;
                if( cnt == 2 ) break;
            }
            if( cnt == 2 ) st.push(make_pair(i, j));
        }
    }
    while( st.size() ){
        cheese[st.top().first][st.top().second] = 0;
        st.pop();
        chee--;
    }
    if( chee == 0 ) return true;
    return false;
}

// in main()
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> cheese[i][j];
            if( cheese[i][j] == 1 ) chee++;
        }
    }
    if( chee == 0 ){
        cout << 0 << endl;
        return 0;
    }
    int d = 1;
    while( 1 ){
        if( func() ) break;
        d++;
    }
    cout << d << endl;

재밌다
안쪽 공기를 어떻게 알지가 고민 됐는데 생각해 보니까 바깥 공기를 bfs로 다 표시해 놓으면 되겠더라
생각해내니까 이전의 내가 멍청해 보인다

그 다음은 쉽다 그냥 바깥 공기와 2개 닿는 것들을 한 번에 0으로 바꾸면 된다.

지금 보니 바깥 공기 배열은 굳이 매번 초기화 안 해도 될 것 같다
처음 한 번만 초기화 후 (0, 0)에서 시작해서 만들어 놓은 후, 그 다음 부터는 바깥 공기에 체크 안 된 부분만 확인해 주면 되겠다
</br>

---

골드 1이 되었다~~ 물렙이지만 기뻐
</br>