1. 9252 - 문자열 / DP

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

https://gusdnr69.tistory.com/192
해당 글을 참고하였다.

해결

#include <iostream>
#include <algorithm>

using namespace std;

int dp[1001][1001] = {
    0,
};
string result;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    string s1, s2;
    cin >> s1 >> s2;

    // s1에서 s2가 있는지 찾음 / s2가 찾을 기준이 되고, i 인덱스
    for (int i = 1; i < s2.size(); i++)
    {
        for (int j = 1; j < s1.size(); j++)
        {
            // 현재 글자가 같다면, 각각 이전의 글자를 탐색, 해당 값에 1을 더함
            if (s1[j] == s2[i])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            // 현재 글자가 같지 않다면, 둘 중에 max를 가짐.
            // 이 부분이 제일 난해.
            else
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    int col = s1.size() - 1;
    int row = s2.size() - 1;

    while (dp[row][col])
    {
        // row와 col을 같다면 다 줄임. 즉 dp값의 시작을 알기 위함.
        if (dp[row][col] == dp[row - 1][col])
        {
            row--;
        }
        else if (dp[row][col] == dp[row][col - 1])
        {
            col--;
        }
        // dp값이 바뀐 시점이 새 글자를 찾은 시점이고, 찾았다면 또 빼고 또 진행.
        else
        {
            result += s1[col];
            row--, col--;
        }
    }

    // LCS알고리즘에 의해, 제일 끝 값이 최대 부분문자열 길이
    cout << dp[s2.size() - 1][s1.size() - 1] << "\n";

    // 출력
    if (result.size() > 0)
    {
        reverse(result.begin(), result.end());
        cout << result << endl;
    }

    return 0;
}

풀이

주석에 다 적어놓았고,
LCS 문제는 DP를 사용해야하는데,
풀이법을 바로 떠올릴 수 없었다.

알고리즘이 그렇게 어렵지는 않으니,
단순히 틀을 외우는 것이 필요해 보인다.

2. - DFS / 구현

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

NxM의 맵에서 벽을 3개만 세울 수 있다.
그렇게 세워서 바이러스가 퍼지지 않는 가장 큰 공간을 답으로 내면 된다.

3개의 벽을 for문에 따라 먼저 세우고,
해당 맵을 DFS를 돌리고 최대값을 비교하여 답으로 내면 될 것 같은데,
엄청난 부하가 걸릴 것으로 예상된다.

그래도 일단 구현해본다.

해결

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int N, M;
int ans = 0;

int cx[4] = {1, 0, -1, 0};
int cy[4] = {0, -1, 0, 1};

int map[9][9];
int tmp[9][9];

void DFS();

// Wall을 2개 생성
void wall(int cur)
{
    // 벽 3개를 전부 세운다면, DFS 진행
    if (cur == 3)
    { 
        DFS();
        return;
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (tmp[i][j] == 0)
            {
                tmp[i][j] = 1;
                wall(cur + 1);
                tmp[i][j] = 0; // 이 행위를 함으로써 모든 경우를 탐지
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> map[i][j];
        }
    }

    // 첫번째 벽을 세우고, 진행
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (map[i][j] == 0)
            {
                copy(&map[0][0], &map[0][0] + 81, &tmp[0][0]); // 복사
                tmp[i][j] = 1;
                wall(1);
                tmp[i][j] = 0; // 이 행위를 함으로써 모든 경우를 탐지
            }
        }
    }

    cout << ans;

    return 0;
}

// 2라면 바이러스를 쭉쭉 진행
void DFS()
{
    int spread[9][9];
    copy(&tmp[0][0], &tmp[0][0] + 81, &spread[0][0]);
    queue<pair<int, int>> q;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (spread[i][j] == 2)
                q.push({i, j});
        }
    }
    while (!q.empty())
    {
        auto cur = q.front();
        q.pop();
        for (int dir = 0; dir < 4; dir++)
        {
            int nx = cur.first + cx[dir];
            int ny = cur.second + cy[dir];
            if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                continue;
            if (spread[nx][ny] == 0)
            {
                spread[nx][ny] = 2;
                q.push({nx, ny});
            }
        }
    }

    // 모든 바이러스가 퍼지고 안전영역을 구함
    int cnt = 0; 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (spread[i][j] == 0)
                cnt++;
        }
    }

    // 최종 ans값 설정
    ans = max(ans, cnt);
}

풀이

다른 사람의 풀이를 보고 풀었다.
Wall 함수를 어떻게 구현해야 할지에서 시간을 굉장히 많이 썼는데,
재귀함수를 통해서 In/Out을 하는 것으로 구현한 것이 충격이었다.

그렇게 벽을 3개 세우면 DFS하고 안전영역 구하면 되는 문제였다.

참고한 사이트
https://chan9.tistory.com/127