약간의 테크닉이 필요한 탐색 문제였다.

예전에 바이러스 관련해서 비슷한 문제를 푼거 같긴한데 로직은 다음과 같다.

1. 불 위치에서 BFS 탐색을 시작해 번지는 시간대를 check 배열에 메모
2. 메모된 check 배열에 따라 지훈이의 위치에서 탐색을 시작
3. 양 모서리 지점까지 도달했으면 탈출한 것으로 체크

딱 봤을 때는 간단한데 1번과 2번을 연동시키는게 좀 생각하기 어렵다. 허나 여러번 풀어보면 간단해보이니 계속 풀어대자

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>
#include <string.h>

#define INF 100000000

using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

char arr[1001][1001];
int check[1001][1001];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
int h, w, sx, sy, fx, fy;
int n, m;

// 불의 위치에서 탐색
void fire_bfs(int x, int y) {
    queue<tiii> q;
    q.push({ x, y, 0 });
    check[x][y] = 0;

    while (!q.empty()) {
        tiii cur = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int cx = get<0>(cur) + dx[i];
            int cy = get<1>(cur) + dy[i];

            if (cx < 1 || cx > n || cy < 1 || cy > n) continue;
            if (arr[cx][cy] == '#') continue;
            if (check[cx][cy] != -1 && check[cx][cy] <= get<2>(cur) + 1) continue;
            // 이미 불이 번진 상태이면 건너뛴다.

            check[cx][cy] = get<2>(cur) + 1;
            q.push({ cx, cy, check[cx][cy] });
        }
    }
}
// 지훈이의 위치에서 탐색
int go_bfs(int x, int y) {
    queue<tiii> q;
    q.push({ x, y, 0 });
    int answer = INF;
    while (!q.empty()) {
        tiii cur = q.front();
        int cur_x = get<0>(cur);
        int cur_y = get<1>(cur);
        int cur_tm = get<2>(cur);
        q.pop();

        if (cur_x == 1 || cur_x == n || cur_y == 1 || cur_y == m) {
            answer = min(answer, cur_tm + 1);
            continue;
        }
        for (int i = 0; i < 4; i++) {
            int cx = get<0>(cur) + dx[i];
            int cy = get<1>(cur) + dy[i];

            if (cx < 1 || cx > n || cy < 1 || cy > m) continue;
            if (arr[cx][cy] != '.') continue;
            if (check[cx][cy] != -1 && check[cx][cy] <= get<2>(cur) + 1) continue;
            // 불이 이미 번져있는 곳이면 갈 수 없다.

            check[cx][cy] = get<2>(cur) + 1;
            q.push({ cx, cy, get<2>(cur) + 1 });
        }
    }
    return answer;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> m;
    string tp;
    vector<pii> fire;
    pii now;

    for (int i = 1; i <= n; i++) {
        cin >> tp;
        for (int j = 1; j <= m; j++) {
            arr[i][j] = tp.at(j - 1);
            if (arr[i][j] == 'F') {
                fire.push_back({ i,j });
            }
            else if (arr[i][j] == 'J') {
                now = { i,j };
            }
        }
    }

    memset(check, -1, sizeof(check));
    for (auto pi : fire)
        fire_bfs(pi.first, pi.second);

    int ans = go_bfs(now.first, now.second);
    if (ans == INF) cout << "IMPOSSIBLE";
    else cout << ans;


    return 0;
}

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

단순한 탐색 문제였다.

직사각형의 범위에 벽이 있나없나만 체크하며 queue 에 넣어주면서 탐색을 진행하면 풀리는 단순한 문제였다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <string.h>

#define INF 100000000

using namespace std;
typedef pair<int, int> pii;
struct Square {
    int x, y;
    int tm;
};

Square initSquare(int _x, int _y, int _tm) {
    Square tp;
    tp.x = _x;
    tp.y = _y;
    tp.tm = _tm;
    return tp;
}

int arr[1001][1001];
int check[1001][1001];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
int h, w, sx, sy, fx, fy;
int n, m;

bool checkSquare(int x, int y) {
    if (x < 1 || x > n || y < 1 || y > m) return false;
    if (y + w - 1 > m || x + h - 1 > n) return false;
    
    for (int i = x; i < x + h; i++) {
        if (arr[i][y] == 1) return false;
        if (arr[i][y + w - 1] == 1) return false;
    }

    for (int i = y; i < y + w; i++) {
        if (arr[x][i] == 1) return false;
        if (arr[x + h - 1][i] == 1) return false;
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
        }
    }
    cin >> h >> w >> sx >> sy >> fx >> fy;

    queue<Square> q;
    q.push(initSquare(sx, sy, 0));
    int answer = INF;
    while (!q.empty()) {
        Square tp = q.front();
        q.pop();

        if (tp.x == fx && tp.y == fy) {
            answer = min(answer, tp.tm);
            continue;
        }
        for (int i = 0; i < 4; i++) {
            int cx = tp.x + dx[i];
            int cy = tp.y + dy[i];
            if (check[cx][cy] == 1) continue;
						// 직사각형의 범위에 벽이 있는지 체크하는 checkSquare
            if (!checkSquare(cx, cy)) continue;

            check[cx][cy] = 1;
            q.push(initSquare(cx, cy, tp.tm + 1));
        }
    }

    if (answer == INF) cout << -1;
    else cout << answer;

    return 0;
}

전형적인 BFS 문제이다.

단순히 길만 따라서 check 배열에 메모 후 탐색, 메모 후 탐색 의 로직으로 문제를 풀게 되면 틀리게 된다. 탐색하는 경우의 수가 사실 2배 더 많기 때문이다.

칼이 있는지, 없는지에 대한 경우를 생각해야 하기 때문에 2배이다. 예를 들어 (2,3) 위치에 이동할 때, 칼을 가진 상태로 이동하는 것과 칼을 가지지 않은 상태로 이동하는 것은 명백히 다른 경우의 수이다. 떄문에 이 두 가지 경우를 다르게 봐야하고 그에 따라 check배열 또한 3차원 배열로 만들어주어야 한다. 그 후에는 다음 코드와 같이 단순히 BFS 탐색을 때리면 끝!

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <string.h>

#define INF 10000000

using namespace std;
typedef pair<int, int> pii;

struct Move {
    int x, y, tm;
    bool sword;
};
Move initMove(int _x, int _y, int _tm, bool _s) {
    Move m;
    m.x = _x;
    m.y = _y;
    m.tm = _tm;
    m.sword = _s;
    return m;
}

int arr[101][101];
int check[101][101][2];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };

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

    int n, m, t;
    cin >> n >> m >> t;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
        }
    }

    queue<Move> q;
    q.push(initMove(1, 1, 0, false));
    check[0][0][0] = 1;
    int min_time = INF;

    while (!q.empty()) {
        Move cur = q.front();
        q.pop();
        if (cur.tm > t) continue;
        if (cur.x == n && cur.y == m) {
            min_time = min(min_time, cur.tm);
            continue;
        }

        for (int i = 0; i < 4; i++) {
            int cx = cur.x + dx[i];
            int cy = cur.y + dy[i];
            if (cx < 1 || cx > n || cy < 1 || cy > m) continue;
            
            if (cur.sword == false) { // 1. 아직 칼을 못찾은 경우
                if (check[cx][cy][0]) continue;
                if (arr[cx][cy] == 1) {
                    continue;
                }
                else if (arr[cx][cy] == 2) { // 1.1. 칼을 찾은 경우
                    check[cx][cy][0] = 1;
                    q.push(initMove(cx, cy, cur.tm + 1, true));
                }
                else if (arr[cx][cy] == 0) { // 1.2. 그냥 길인 경우
                    check[cx][cy][0] = 1;
                    q.push(initMove(cx, cy, cur.tm + 1, false));
                }
            }
            else if (cur.sword == true) { // 2. 칼을 찾은 경우
                if (check[cx][cy][1]) continue;
                check[cx][cy][1] = 1;
                q.push(initMove(cx, cy, cur.tm + 1, true));
            }
        }

    }
    if (min_time == INF)
        cout << "Fail";
    else
        cout << min_time;

    return 0;
}

모든 경우이 수를 다 보는 것은 1초의 제한시간과 30만의 입력값을 보았을 때 당연히 되지 않는구나~ 라고 느껴야 한다.

때문에 뭔가 다른 방법을 생각해야 한다. 이 문제의 경우는 인접한 수끼리의 차를 정렬한 뒤 N-K 만큼 앞부터 원소를 고르는 식으로 집합을 생각하면 간단하다. 이와 같이 구현만 하면 문제는 간단히 풀린다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
deque<int> arr;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a, b;
    cin >> a >> b;
    
    int cur, prev = 0;
    for (int i = 0; i < a; i++) {
        cin >>  cur;
        if (prev == 0) {
            prev = cur;
            continue;
        }
        else {
            arr.push_back(cur - prev);
            prev = cur;
        }
    }

    sort(arr.begin(), arr.end());

    LL res = 0;
    for (int k = 0; k < a-b; k++) {
        int cx = arr.front();
        arr.pop_front();
        res += cx;
    }
    cout << res;
    // 2 2 1 5
    return 0;
}

경우를 잘 나눠야 하는 문제이다. 일단 문제의 시간제한 1초를 봤을 때 10만의 입력값으로 통과하기 위해서는 답은 O(Nlog(N)) 의 시간 제한으로 풀 수 있어야 한다. 때문에 이분탐색, 세그먼트 트리 등등의 알고리즘을 떠올릴 수 있다.

이 문제의 경우에는 다른 자료구조가 필요한 것이 아니라 전체 경우가 최대값을 가지기 위해서는 특정 경우로 나뉜다 정도만 알면 풀 수 있다.

전체 최대값을 가질 수 있는 경우는 다음과 같다.

1. "벌꿀 - 벌 - 벌" 순서로 있는 경우
2. "벌 - 벌 - 벌꿀" 순서로 있는 경우
3. "벌 - 벌꿀 - 벌" 순서로 있는 경우

각 경우마다 왼쪽 끝, 오른쪽 끝에 위치해야하고, 중간 특정 지점이 위치해야 한다.

위 3가지 경우에 대해 값을 다 확인하며 최대값을 구할 때 O(N) 의 복잡도를 이끌어 내기 위하여 누적합을 왼쪽, 오른쪽 방향으로 구해놓아야 한다. 그 후에는단순 선형탐색을 통해 답을 빠르게 구할 수 있다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
int arr[100001];
int r_sum[100001];
int l_sum[100001];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        l_sum[i] = (i == 0) ? arr[i] : l_sum[i-1] + arr[i];
    }
    for (int i = n - 1; i >= 0; i--)
        r_sum[i] = (i == n-1) ? arr[i] : r_sum[i+1] + arr[i];
    

    int _max = 0;
    for (int i = 1; i < n - 1; i++) 
        if(_max < arr[i]) _max = arr[i];
    
    int answer = 0, a_res, c_res;
    for (int i = 1; i < n - 1; i++) {
        a_res = 0;
        // 오른쪽 끝이 벌꿀인 경우
        a_res += r_sum[i] - arr[i];
        a_res += r_sum[0] - arr[0] - arr[i];
        answer = max(answer, a_res);
				
				// 왼쪽 끝이 벌꿀인 경우
        c_res = 0;
        c_res += l_sum[i] - arr[i];
        c_res += l_sum[n - 1] - arr[n - 1] - arr[i];
        answer = max(answer, c_res);
    }

		// 가운데에 벌꿀이 있는 경우
    cout << max(answer, l_sum[n - 1] - arr[0] - arr[n - 1] + _max);
    
    return 0;
}

heap 2개를 가지고 Nlog(N) 의 시간 내로 중앙값을 뽑아내는 로직을 사용하면 쉽게 풀린다. heap 2개는 다음과 같다.

• 절반의 작은 값들을 저장하는 max heap
• 절반의 큰 값들을 저장하는 min heap

이 때 min heap 이 max heap 크기 이상의 특징을 계속 가지도록 한다면 홀 수 개의 값이 입력되었을 때 min heap 의 top 을 출력하도록 하면 쉽게 풀린다.

예를 들어 입력되는 수가 1, 5, 4, 3, 2 라고 해보자.

1. 1 이 들어오게 되면 먼저 min heap 에 넣는다.
2. 그 후 5가 들어오면 size 가 작은 max heap 에 넣는다.
3. 넣은 후 max heap 의 top과 min heap의 top 을 비교해서 max heap 의 것이 더 크다면 서로 top 을 swap 해준다.
4. 2~3 을 반복한다.

이렇게 되면 위에서 말했듯이 절반의 작은 값들은 max heap 에 저장되고, 절반의 큰 값들은 min heap 에 저장되어 중간값을 바로바로 꺼내어 확인할 수 있게 된다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long LL;

int n, m;
int arr[10001];
priority_queue<int, vector<int>, greater<int>> minQ;
priority_queue<int, vector<int>, less<int>> maxQ;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int tc;
    cin >> tc;
    vector<int> ans;
    for (int i = 0; i < tc; i++) {
        cin >> n;
        ans.clear();
        memset(arr, 0, sizeof(arr));
        for (int j = 1; j <= n; j++) {
            cin >> arr[j];

            if (minQ.empty()) 
                minQ.push(arr[j]);
            else if (minQ.size() > maxQ.size()) 
                maxQ.push(arr[j]);
            else if (maxQ.size() <= maxQ.size()) 
                minQ.push(arr[j]);
            // 똑같음
            if (!maxQ.empty() && maxQ.top() > minQ.top()) {
                int temp = maxQ.top();
                maxQ.pop();
                maxQ.push(minQ.top());
                minQ.pop();
                minQ.push(temp);
            }

            if (j % 2 != 0) {
                ans.push_back(minQ.top());
            }
        }
        cout << ans.size() << endl;
        for (int i = 0, cnt = 0; i < ans.size(); i++) {
            cout << ans[i] << " ";
            cnt += 1;
            if (cnt % 10 == 0) cout << endl;
        }
        cout << endl;

        while (!maxQ.empty()) maxQ.pop();
        while (!minQ.empty()) minQ.pop();
    }

    return 0;
}

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

시간 복잡도가 1초이고, 입력값이 10만개, query 의 값이 만개 이므로 각 query 마다 log(N) 의 복잡도 내로 답이 나오도록 처리해야 문제가 풀리게 된다.

이를 위해 입력 시에만 Nlog(N) 의 복잡도가 걸리고 query 에 따른 값을 뽑아 낼 때는 log(N) 의 복잡도를 가지는 min heap, max heap 2개와 solved 된 문제를 체킹하기 위한 배열 1개가 잇으면 간단히 풀리게 된다.

단, solved 된 문제를 체킹할 때 해당 문제의 난이도를 배열에 저장함으로써 이 후 top 의 값이 체킹해두었던 난이도가 아니라면 pop 하고 다음 수를 보는 로직을 통해 문제를 해결할 수 있다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long LL;

int n, a, b;
string tp;
int check[100001];
priority_queue<pii, vector<pii>, greater<pii>> minQ;
priority_queue<pii, vector<pii>> maxQ;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        maxQ.push({ b, a });
        minQ.push({ b, a });
        check[a] = b;
    }

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> tp;
        if (tp == "add") {
            cin >> a >> b;
            maxQ.push({ b, a });
            minQ.push({ b, a });
            check[a] = b;
        }
        else if (tp == "recommend") {
            cin >> a;
            if (a == 1) {
                while (check[maxQ.top().second] != maxQ.top().first) {
                    maxQ.pop();
                }
                cout << maxQ.top().second << endl;
            }
            else if (a == -1) {
                while (check[minQ.top().second] != minQ.top().first) {
                    minQ.pop();
                }
                cout << minQ.top().second << endl;
            }
        }
        else if (tp == "solved") {
            cin >> a;
            check[a] = -1;
        }
    }
    return 0;
}

단순한 그래프 탐색을 진행하게 되면 바로 시간이 터지게 된다.

오른쪽위 → 오른쪽 → 오른쪽 아래 순으로 탐색을 하는 그리디 1, 빵집의 가스관 위쪽부터 차례대로 파이프를 연결할 수 있나? 없나? 를 확인하며 파이프를 만드는 방식의 그리디 2 총 2개의 2그리디 방식을 사용해야 한다.

첫 번째 그리디의 경우 어찌저찌 잘 생각할 수 있겠지만, 두 번째 그리디의 경우에는 생각하기 어려워서.. 매우 오랜 시간이 걸린 문제이다.

로직은 다음과 같다.

• 빵집의 가스관 위쪽 부터 dfs 탐색을 돌며 파이프를 만들 수 있는지 확인한다.
• ( 만들 수 있으면 response 에 +1, 없으면 +0 을 해준다. )

그리디만 알면 생각보다 간단한 문제이나 생각하기 힘들다... 

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long LL;

int n, m;
char arr[10001][501];
int check[10001][501];
int dx[] = { -1,0, 1 };
int dy[] = { 1, 1, 1 };
int _max = 0;
vector<pii> pla;

bool dfs(int x, int y) {
    check[x][y] = 1;
    if (y == m) return true;
    for (int i = 0; i < 3; i++) {
        int cx = x + dx[i];
        int cy = y + dy[i];

        if (cx < 1 || cx > n || cy < 1 || cy > m) continue;
        if (check[cx][cy] || arr[cx][cy] == 'x') continue;

        bool flag = dfs(cx, cy);
        if (flag) return true;
    }
    return false;

}
int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf(" %1c", &arr[i][j]);
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i++) {
        res += dfs(i, 1);
    }

    cout << res;

    return 0;
}

시간 복잡도가 중요한 문제이다. 일단 제한 시간을 보면 10초인 것을 볼 수 있다.

허나 입력값이 100개인 배열에서 일일이 다 비숍을 넣어가면서 백트래킹을 하게 된다면 O(2^(10*10)) 이 되어 터져버리게 된다.

이를 위해 체스판의 특징을 생각해 흑,백 으로 나눠 로직을 짜보려고 한다. 이렇게 되면 복잡도가 O(2^(5*5)) 가 되어 문제 없이 제한시간을 맞추게 된다. 분할해서 생각한다면 로직은 일반 백트래킹과 다를바 없어 넘어가도록 하겠다.

다만 흑,백으로 나누어 check 배열을 두고 확인하는 로직만 유심히 보면 될것 같다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long LL;

int N;
int chess[11][11];
int color[11][11];
int check[11][11];
int dx[] = { -1,1,1,-1 };
int dy[] = { 1,-1,1,-1 };
int max_cnt[2]; 
vector<vector<pii>> zero(2);

bool check_bis(int cx, int cy) {
    for (int i = 0; i < 4; i++) {
        int nx = cx + dx[i];
        int ny = cy + dy[i];

        for (int j = 1; j < N; j++) {
            if (nx < 1 || nx > N || ny < 1 || ny > N) continue;
            if (check[nx][ny]) return false;

            nx += dx[i];
            ny += dy[i];
        }
    }
    return true;
}

void dfs(int n, int cnt, int col) {
    max_cnt[col] = max(cnt, max_cnt[col]);
    if (n + 1 >= zero[col].size()) 
        return;
    
    for (int i = n + 1; i < zero[col].size(); i++) {
        int cx = zero[col][i].first;
        int cy = zero[col][i].second;
        if (color[cx][cy] != col) continue;
        if (check[cx][cy] == 1) continue;
        if (!check_bis(cx, cy)) continue;
        if (chess[cx][cy] == 0) continue;

        check[cx][cy] = 1;
        dfs(i, cnt + 1, col);
        check[cx][cy] = 0;
    }
}

int main() {
    cin >> N;
    int input;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> chess[i][j];
            if ((i + j) % 2 == 0) { 
            // 백색 : 1, 흑색 : 0
                color[i][j] = 0;
                if(chess[i][j]) zero[0].push_back({ i,j });
            }
            else if ((i + j) % 2 == 1) {
                color[i][j] = 1;
                if (chess[i][j]) zero[1].push_back({ i,j });
            }
        }
    }

    dfs(-1, 0, 0);
    dfs(-1, 0, 1);
    
    printf("%d", max_cnt[0] + max_cnt[1]);
    return 0;
}