[모각코] 8회차

우리가치 모각코 8회차

 

1. 일시

👉🏻 2022년 11월 08일

2. 장소 

👉🏻 성곡도서관 지하 1층 카페 인피니티 / 예술관 카페

 

3. 학습내용

오늘은 각자 풀고 싶은 알고리즘 문제를 정하고, 풀어보는 시간을 갖었다.

오늘도 저번과 같이 BFS, DFS 관련 알고리즘 문제를 풀어보았다.

 

#4179

내가 정한 첫 번째 문제는4179번의 불! 문제다.

이 문제는 탈출 조건이 있어 x와 y좌표가 0보다 작고, n보다 클 때 탈출이 가능하다는 것이 기존 조건과 달라 잘 기억해둬야 할 문제라고 생각한다.

#include <iostream>
#include <queue>
#include <string>
using namespace std;
#define MX 1001
struct strt
{
    int x;
    int y;
};
char board[MX][MX];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int dt1[MX][MX];
int dt2[MX][MX];
queue<strt> Q1;
queue<strt> Q2;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int r, c;

    cin >> r >> c;
    for (int i = 0; i < r; ++i)
    {
        fill(dt1[i], dt1[i] + c, -1);
        fill(dt2[i], dt2[i] + c, -1);
    }
    string s;
    for (int i = 0; i < r; ++i)
    {
        cin >> s;
        for (int j = 0; j < c; ++j)
        {
            board[i][j] = s[j];
            if (board[i][j] == 'F')
            {
                Q1.push({i, j});
                dt1[i][j] = 0;
            }
            else if (board[i][j] == 'J')
            {
                Q2.push({i, j});
                dt2[i][j] = 0;
            }
        }
    }
    while (!Q1.empty())
    {
        strt cur = Q1.front();
        Q1.pop();

        for (int d = 0; d < 4; ++d)
        {
            int nx = cur.x + dx[d];
            int ny = cur.y + dy[d];
            if (nx < 0 || r <= nx || ny < 0 || c <= ny)
                continue;
            if (dt1[nx][ny] >= 0 || board[nx][ny] == '#')
                continue;
            dt1[nx][ny] = dt1[cur.x][cur.y] + 1;
            Q1.push({nx, ny});
        }
    }
    while (!Q2.empty())
    {
        strt cur = Q2.front();
        Q2.pop();

        for (int d = 0; d < 4; ++d)
        {
            int nx = cur.x + dx[d];
            int ny = cur.y + dy[d];
            if (nx < 0 || r <= nx || ny < 0 || c <= ny)
            {
                cout << dt2[cur.x][cur.y] + 1 << "\n";
                return 0;
            }
            if (dt2[nx][ny] >= 0 || board[nx][ny] == '#')
                continue;
            if (dt1[nx][ny] != -1 && dt1[nx][ny] <= dt2[cur.x][cur.y] + 1)
                continue;
            dt2[nx][ny] = dt2[cur.x][cur.y] + 1;
            Q2.push({nx, ny});
        }
    }
    cout << "IMPOSSIBLE"
         << "\n";
    return 0;
}

 

#5427

내가 정한 두 번째 문제는 5427번의 불 문제인데, 이 문제는 위 문제와 비슷하면서도 다른 문제다. 이 문제를 처음 틀렸던 이유는, 불이 와야 움직일 수 있다는 것을 고려하지 못하고 위와 비슷할 것이라고만 생각하고 코드를 작성했기 때문이었다.

#include <iostream>
#include <queue>
#include <string>
using namespace std;
#define MX 1001
int tc, w, h;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
char board[MX][MX];
int dt1[MX][MX];
int dt2[MX][MX];
struct strt
{
    int x;
    int y;
};
queue<strt> q1;
queue<strt> q2;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> tc;
    while (tc--)
    {
        cin >> w >> h;
        string s;
        bool flag = false;
        for (int i = 0; i < h; ++i)
        {
            fill(dt1[i], dt1[i] + w, -1);
            fill(dt2[i], dt2[i] + w, -1);
        }
        q1 = queue<strt>();
        q2 = queue<strt>();

        for (int i = 0; i < h; ++i)
        {
            cin >> s;
            for (int j = 0; j < w; ++j)
            {
                board[i][j] = s[j];
                if (board[i][j] == '*')
                {
                    dt1[i][j] = 0;
                    q1.push({i, j});
                }
                else if (board[i][j] == '@')
                {
                    dt2[i][j] = 0;
                    q2.push({i, j});
                }
            }
        }

        while (!q1.empty())
        {
            strt cur = q1.front();
            q1.pop();
            for (int d = 0; d < 4; ++d)
            {
                int nx = cur.x + dx[d];
                int ny = cur.y + dy[d];

                if (nx < 0 || h <= nx || ny < 0 || w <= ny)
                    continue;
                if (dt1[nx][ny] >= 0 || board[nx][ny] == '#')
                    continue;
                dt1[nx][ny] = dt1[cur.x][cur.y] + 1;
                q1.push({nx, ny});
            }
        }

        while (!q2.empty())
        {
            strt cur = q2.front();
            q2.pop();
            for (int d = 0; d < 4; ++d)
            {
                int nx = cur.x + dx[d];
                int ny = cur.y + dy[d];

                if (nx < 0 || h <= nx || ny < 0 || w <= ny)
                {
                    cout << dt2[cur.x][cur.y] + 1 << "\n";
                    flag = true;
                    break;
                }
                if (dt2[nx][ny] >= 0 || board[nx][ny] == '#')
                    continue;
                if (dt1[nx][ny] != -1 && dt1[nx][ny] <= dt2[cur.x][cur.y] + 1)
                    continue;
                dt2[nx][ny] = dt2[cur.x][cur.y] + 1;
                q2.push({nx, ny});
            }

            if (flag)
                break;
        }
        if (!flag)
            cout << "IMPOSSIBLE\n";
    }
    return 0;
}

 

4. 소감(느낀 점)

비슷한 문제를 풀면서 개념을 익히려고 바로 비슷한 문제를 풀어보려고 한건데, 오히려 기억에 의존해서 문제를 풀게 되는 것 같았다. 

비슷한 문제일수록 시간을 두고 푸는 것이 더 효과적으로 학습할 수 있는 방법이라 느꼈고, 앞으로는 비슷한 문제를 기록하고, 시간을 두어 풀어보는 연습을 해야되겠다.

 

 

---

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

4179번: 불!

 

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

5427번: 불

https://www.youtube.com/c/BaaarkingDog/videos

BaaarkingDog