cyj893

저장소

백준: Class 3 ⑧ - 14500, 16236

3 분 소요


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

14500: 테트로미노

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

귀찮은… 문제다

1. ㅓ, ㅏ, ㅗ, ㅜ 제외

int mmap[501][501];
int visited[501][501];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void func(int x, int y, int d, int sum){
    visited[x][y] = 1;
    sum += mmap[x][y];
    if( d == 4 ){
        ans = max(ans, sum);
        return;
    }
    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( visited[nx][ny] == 0 ){
            func(nx, ny, d+1, sum);
            visited[nx][ny] = 0;
        }
    }
}

// in main()
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            func(i, j, 1, 0);
            visited[i][j] = 0;
        }
    }

ㅓ, ㅏ, ㅗ, ㅜ를 제외한 모양들은 dfs로 쭉쭉 뻗어 나가면 찾을 수 있다. ㅓ 얘는 하나에 여러 개 달린 모양이라 못 한다.
4개를 채울 때마다 ans를 최대값으로 업데이트 해 준다.
</br>

2. ㅓ, ㅏ, ㅗ, ㅜ 처리

int dxy[4][3][2] = {
    { {-1, 0}, {1, 0}, {0, -1} }, // ㅓ
    { {0, -1}, {0, 1}, {-1, 0} }, // ㅗ
    { {-1, 0}, {1, 0}, {0, 1} },  // ㅏ
    { {0, -1}, {0, 1}, {1, 0} },  // ㅜ
};

// in main()
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            for(int k = 0; k < 4; k++){
                int nx1 = i + dxy[k][0][0];
                int ny1 = j + dxy[k][0][1];
                if( nx1 < 0 || ny1 < 0 ) continue;
                int nx2 = i + dxy[k][1][0];
                int ny2 = j + dxy[k][1][1];
                if( n <= nx2 || m <= ny2 ) continue;
                int nx3 = i + dxy[k][2][0];
                int ny3 = j + dxy[k][2][1];
                if( nx3 < 0 || ny3 < 0|| n <= nx3 || m <= ny3 ) continue;
                ans = max(ans, mmap[i][j] + mmap[nx1][ny1] + mmap[nx2][ny2] + mmap[nx3][ny3]);
            }
        }
    }

ㅓ, ㅏ, ㅗ, ㅜ는 중심점에 3개가 달린 모습이다.
그래서 이중 포문으로 모든 점에 접근해서, 그 점이 중심일 때 가능한 경우를 다 살펴 봤다.
세 점들이 인덱스 범위 밖에 나가면 안 되니까 확인 해준다.
</br>

16236: 아기 상어

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

int func(int k, int cnt){
    int fx = -1, fy = -1, dd = -1;
    vector< pair<int, int> > v;
    priority_queue< tuple<int, int, int>, vector<tuple<int, int, int>>, greater<> > pq;
    pq.push(make_tuple(0, sx, sy));
    while( pq.size() ){
        int d = get<0>(pq.top());
        int x = get<1>(pq.top());
        int y = get<2>(pq.top());
        pq.pop();
        if( mmap[x][y] != 0 && mmap[x][y] < k ){
            fx = x;
            fy = y;
            dd = 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 || n <= ny ) continue;
            if( mmap[nx][ny] <= k && visited[nx][ny] == 0 ){
                pq.push(make_tuple(d+1, nx, ny));
                visited[nx][ny] = 1;
            }
        }
    }
    if( fx == -1 ) return 0;
    ans += dd;
    mmap[sx][sy] = 0;
    sx = fx;
    sy = fy;
    mmap[fx][fy] = 0;
    return cnt+1;
}

// in main()
    int k = 2;
    int cnt = 0;
    while( 1 ){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                visited[i][j] = 0;
            }
        }
        cnt = func(k, cnt);
        if( cnt == 0 ) break;
        if( cnt == k ){
            k++;
            cnt = 0;
        }
    }
    cout << ans << endl;

유의할 점

  1. 상어보다 큰 곳은 못 지나 감
  2. 그냥 bfs 사용하면 탐색 순서 안 맞아서 안 됨. 우선순위 큐에 넣어서 <거리, i, j> 튜플로 넣으면 잘 정렬 된다(거리 작은 순, 거리 같으면 세로 작은 순(위쪽), 위쪽 같으면 가로 작은 순(왼쪽))
  3. 혹시 출력 확인 한다고 상어 위치 9로 표시해 두면 무한루프 되니까 꼭 지우기

예제 출력

ex) 4
4 3 2 1
0 0 0 0
0 0 9 0
1 2 3 4

크기: 2 1
Ans: 3
4 3 2 9
0 0 0 0
0 0 0 0
1 2 3 4

크기: 3 0
Ans: 9
4 3 2 0
0 0 0 0
0 0 0 0
9 2 3 4

크기: 3 1
Ans: 10
4 3 2 0
0 0 0 0
0 0 0 0
0 9 3 4

크기: 3 2
Ans: 14
4 3 9 0
0 0 0 0
0 0 0 0
0 0 3 4


</br>

두 번째 문제 상어 재밌네
</br>

댓글남기기

참고