집배원 한상덕

코드

[ 시간초과 코드 ]

#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <numeric>
#include <map>
#include <stack>
#define ull unsigned long long
using namespace std;
int N, ans=1e9, house_cnt;
char board[52][52]; // 1 ~ N
int height[52][52];
int cost[2502][52][52];
int dr[8] = {0, 1, 0, -1, -1, -1, 1, 1};
int dc[8] = {1, 0, -1, 0, -1, 1, -1, 1};
pair<int,int> post;
struct info{
    int r;
    int c;
    int find=0;
    int max_height=0;
    int min_height=0;
    map<pair<int,int>,bool> m;
};
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
        {
            cin >> board[i][j];
            if(board[i][j] == 'P') post = {i,j};
            else if(board[i][j] == 'K') house_cnt++;
        }

    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            cin >> height[i][j];

    queue<info> q; 
    info st = {post.first, post.second, 0, height[post.first][post.second], height[post.first][post.second]};
    q.push(st);
    cost[0][post.first][post.second] = 1e9;
    while(!q.empty())
    {
        info cur = q.front(); q.pop();
        for(int dir=0;dir<8;dir++)
        {
            info next = cur;
            int nr = cur.r + dr[dir];
            int nc = cur.c + dc[dir];
            int find = cur.find;
            if(nr<1 or nc<1 or nr>N or nc>N) continue;
            if(board[nr][nc] == 'K' and !next.m[{nr,nc}]) {
                next.m[{nr,nc}] = true; // 같은 'K'를 방문해서 count채울 수 없게 함
                find++;
            }
            next.r = nr; next.c = nc; next.find = find;
            next.min_height = min(next.min_height, height[nr][nc]);
            next.max_height = max(next.max_height, height[nr][nc]);
            if(cost[find][nr][nc] != 0 and cost[find][nr][nc] <= next.max_height - next.min_height) continue;
            cost[find][nr][nc] = next.max_height - next.min_height;
            if(find == house_cnt){
                ans = min(ans, next.max_height - next.min_height);
                continue;
            }
            q.push(next);
        }
    }
    cout << ans;
    return 0;
}

• 핵심 원리
  • 3차원 cost를 사용 + queue에 info라는 구조체를 통해 정보 관리
  • cost[찾은K개수][R][C]
  • info = { r / c / find / max_height / min_height / m }
       --> m이라는 map을 통해서 같은 자리에 대한 K를 중복 find할 수 없게 설계

• 문제점
  : 시간초과 --> 시간복잡도는..?

[ 정답풀이 - 2포인터 + BFS/DFS ]

#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <numeric>
#include <map>
#include <stack>
#define ull unsigned long long
using namespace std;
int dr[8] = {0, 1, 0, -1, -1, -1, 1, 1};
int dc[8] = {1, 0, -1, 0, -1, 1, -1, 1};
int N, ans=1e9, house_cnt;
char board[52][52]; // 1 ~ N
int height[52][52];
bool vis[52][52];
vector<int> fatigue;
pair<int,int> post;
struct info{
    int r;
    int c;
    int find=0;
    int max_height=0;
    int min_height=0;
    map<pair<int,int>,bool> m;
};
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
        {
            cin >> board[i][j];
            if(board[i][j] == 'P') post = {i,j};
            else if(board[i][j] == 'K') house_cnt++;
        }

    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
        {
            cin >> height[i][j];
            fatigue.push_back(height[i][j]);
        }
    sort(fatigue.begin(), fatigue.end());
    fatigue.erase(unique(fatigue.begin(), fatigue.end()), fatigue.end());

    int left = 0;
    int right = 0;
    while(right < fatigue.size() and left < fatigue.size())
    {
        int cur_fatigue = height[post.first][post.second];
        // 시작 높이가 범위에 없으면 right++ & pass
        if(cur_fatigue < fatigue[left] or cur_fatigue > fatigue[right]) {
            right++;
            continue;
        }
        /* BFS 시작 */
        queue<pair<int,int>> q;
        int find=0;
        for(int i=1;i<=N;i++)
            fill(vis[i]+1, vis[i]+N+1, false);
        vis[post.first][post.second] = true;
        q.push(post);
        while(!q.empty())
        {
            auto cur = q.front(); q.pop();
            for(int dir=0;dir<8;dir++)
            {
                int nr = cur.first + dr[dir];
                int nc = cur.second + dc[dir];
                if(nr<1 or nc<1 or nr>N or nc>N) continue;
                if(vis[nr][nc] or (height[nr][nc]>fatigue[right] or height[nr][nc]<fatigue[left])) continue;
                if(board[nr][nc] == 'K') find++;
                q.push({nr, nc});
                vis[nr][nc] = true;
            }
        }
        /* 모든 집에 방문했는지 검사 */
        if(find == house_cnt) {
            ans = min(ans, fatigue[right] - fatigue[left]);
            left++; // 최소값이 더 작은 경우가 나올 수 있기 때문
        }
        else right++;
    }
    cout << ans;
    return 0;
}

• 핵심 원리
  • 모든 고도를 입력받은 뒤 중복을 제거한 fatigue를 만들어야 한다
  • fatigue에 대해서 2포인터 + BFS 를 이용
    : left / right를 두고 fatigue를 순회하며 높이값을 조절해서 가능한 범위를 탐색해야 한다

• 주의
  • fatigue 탐색시 반드시 시작의 height(고도)가 범위 안에 있을 때만 BFS 수행!
    --> 없다면 right++로 범위 확대
  • 탐색에 성공했을 때 바로 종료하는것이 아니라, left++로 더 작은 경우에 가능한지 검사해야함!

• 시간복잡도
  • 고도의 범위는 10^6까지지만 어차피 개수는 최대 O(N*M)개에 대해서만 수행된다
  • BFS의 시간복잡도는 O(N^2)
  • 총 = O(N*M*N^2) = O(N^3*M) = O(10^4)

• 느낀 점
  • 2포인터 + BFS/DFS 를 사용하는 유형이 종종 나타난다고 하니 기억해두면 좋을 것 같다