P4 2842 집배원 한상덕

2시간 51분 50초
고도를 정렬하고 중복 제거 한 후 투포인터를 이용해서 차이가 가장 적은 고도를 구하는 문제다.
투포인터도 생각 못하고 탐색 알고리즘으로 삽질해서 시간을 말도 안 되게 소모했다. 반성하자.

코드

#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <unordered_map>
#include <climits>

#define INF 987654321
#define INF2 2147483647
#define f first
#define s second
#define all(v) (v).begin(), (v).end()

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;

int N, K=0;
char grid[50][50];
int height[50][50];
pii office;
vector<int> heightSort;

int dx[] = {-1,-1,-1,0,0,1,1,1};
int dy[] = {-1,0,1,-1,1,-1,0,1};


bool check(int low, int high) {
    int cnt = 0;
    bool visited[50][50];
    memset(visited, 0, sizeof visited);
    queue<pii> q;

    // BFS
    visited[office.f][office.s] = true;
    q.emplace(office);
    while(!q.empty()) {
        int x = q.front().f, y = q.front().s;
        q.pop();
        if(grid[x][y] != '.') cnt++;

        for(int d=0; d<8; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if(nx < 0 || nx >= N || ny < 0 || ny >= N || visited[nx][ny]) continue;
            if(!(low <= height[nx][ny] && height[nx][ny] <= high)) continue;
            visited[nx][ny] = true;
            q.emplace(nx,ny);
        }
    }

    return cnt == K;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N;
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            cin >> grid[i][j];
            if(grid[i][j] != '.') K++;
            if(grid[i][j] == 'P') office = pii(i, j);
        }
    }
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            cin >> height[i][j];
            heightSort.emplace_back(height[i][j]);
        }
    }
    sort(all(heightSort));
    heightSort.erase(unique(all(heightSort)), heightSort.end());


    int ans = INF;
    auto left = heightSort.begin(), right = heightSort.begin();
    while(left <= right && right != heightSort.end()) {
        //최고 높이가 우체국 보다는 높아야 한다.
        if(*right < height[office.f][office.s]) {
            right++;
            continue;
        }
        //최저 높이가 우체국 보다는 낮아야 한다.
        if(height[office.f][office.s] < *left) break;

        if(check(*left, *right)) {
            ans = min(ans, *right - *left);
            left++;
        }
        else right++;
    }
    cout << ans << '\n';

    return 0;
}

코드 설명

• left, right 투 포인터를 이용해 가장 차이가 적은 고도의 low, high를 탐색했다.
• 해당 left, right일 때 한상덕 씨가 모든 집에 들릴 수 있는지를 확인해야 하는데 BFS로 방문 가능한 지 확인했다.

추가

//최저 높이가 우체국 보다는 낮아야 한다.
if(height[office.f][office.s] < *left) break;

이 코드를 뺐더니 시간 초과도 아니고 틀렸습니다가 나왔다.
생각해보니 check함수 즉, 모두 방문할 수 있는지를 확인할 때 시작점이 우체국이어서 우체국은 무조건 방문할 수 있도록 left, right 값이 조정되어야 한다.

P4 9376 탈옥

2시간 30분 11초
탈옥의 경우의 수는 다음과 같다.

1. 죄수1과 죄수2가 만나지 않고 따로 나갈 때
2. 죄수1과 죄수2가 중간에 만나서 같이 나갈 때

우선순위 다익스트라를 이용해서

1. 죄수1과 죄수2가 각각 이동하는데 열어야 하는 문의 최소 수를 구한다.
2. 각 지점에서 밖으로 나가기 위해 열어야 하는 문의 최소 수를 구한다.

1번은 다익스트라를 이용하면 쉽게 구할 수 있으나 2번은 조금 변형을 해줘야 한다.
바깥으로 나갈 수 있는 모든 지점을 시작점으로 해서 다익스트라를 적용시키면 2번을 구할 수 있다.

코드

#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <unordered_map>
#include <climits>

#define INF 987654321
#define INF2 2147483647
#define f first
#define s second
#define all(v) (v).begin(), (v).end()

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ti3 = tuple<int, int, int>;

int h, w;
char grid[100][100];
int openForEscape[100][100]; // openForEscape[x][y]: (x,y)에서 밖으로 나갈 때까지 열어야 하는 문의 최솟값
int prisoner1[100][100], prisoner2[100][100];
vector<pii> prisoner; // 죄수1,2의 시작 위치
vector<pii> outdoor;

int dx[] = {0,0,-1,1};
int dy[] = {1,-1,0,0};

bool outOfRange(int x, int y) {
    return x < 0 || x >= h || y < 0 || y >= w;
}
void dijkstra(int sx, int sy, int dist[][100]) {
    priority_queue<ti3, vector<ti3>, greater<>> pq;

    dist[sx][sy] = (grid[sx][sy] == '#');
    pq.emplace(dist[sx][sy], sx, sy);
    while(!pq.empty()) {
        int opened = get<0>(pq.top()), x = get<1>(pq.top()), y = get<2>(pq.top());
        pq.pop();
        if(dist[x][y] < opened) continue;
        for(int d=0; d<4; d++) {
            int nx = x+dx[d] ,ny = y+dy[d];
            if(outOfRange(nx,ny) || grid[nx][ny] == '*') continue;
            int nextOpened = opened + (grid[nx][ny] == '#');
            if(dist[nx][ny] <= nextOpened) continue;
            dist[nx][ny] = nextOpened;
            pq.emplace(nextOpened, nx, ny);
        }
    }

}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T; cin >> T;
    while(T--) {
        prisoner.resize(0);
        outdoor.resize(0);
        cin >> h >> w;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> grid[i][j];
                if (grid[i][j] == '$') prisoner.emplace_back(i, j);
                if (grid[i][j] != '*' && (i==0 || i==h-1 || j==0 || j==w-1)) outdoor.emplace_back(i,j);
            }
        }
        fill(&openForEscape[0][0], &openForEscape[99][100], INF);
        for(pii out : outdoor) {
            dijkstra(out.f, out.s, openForEscape);
        }
        fill(&prisoner1[0][0], &prisoner1[99][100], INF);
        fill(&prisoner2[0][0], &prisoner2[99][100], INF);
        dijkstra(prisoner[0].f, prisoner[0].s, prisoner1);
        dijkstra(prisoner[1].f, prisoner[1].s, prisoner2);
        int min1 = INF, min2 = INF;
        for(pii out : outdoor) {
            min1 = min(min1, prisoner1[out.f][out.s]);
            min2 = min(min2, prisoner2[out.f][out.s]);
        }
        int ans = min1 + min2;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if(openForEscape[i][j] == INF || prisoner1[i][j] == INF || prisoner2[i][j] == INF) continue;
                int res = openForEscape[i][j] + prisoner1[i][j] + prisoner2[i][j] - 2*(grid[i][j] == '#');
                ans = min(ans, res);
            }
        }
        cout << ans << '\n';
    }



    return 0;
}

코드 설명

주의해야 할 점이 있다.
(i,j)에서 죄수1,2가 만나서 같이 탈출하는 경우를 계산할 때 (i,j)에 문이 있다면 해당 문을 3번 여는 것처럼 계산해버린다. 이 때문에 2를 빼줘야 한다.

후기

생각 자체는 바로 했는데 구현에서 삽질했다. 덕분에 코드 하나씩 뜯어보면서 고치느라 말도 안되게 오래 걸렸다.
여러 테스트케이스인 경우는 변수 초기화에 신경쓰자. outdoor 배열을 매 테스트 케이스마다 초기화시켜주는 걸 빼먹어서 헤맸다...