[TIL] 24.02.07

1. 알고리즘 문제 해결

 

 

불(백준 5427):

 이것도 BFS로 풀 수 있다. 불이 옮겨진 칸을 비롯해 불이 붙으려는 칸도 이동할 수 없으므로, 시간이 지났을 때 불의 번짐처리를 먼저 해주면 된다. 처음에 메모리를 아끼겠답시고, 방문 행렬을 따로 사용하지 않고 기존의 지도 행렬에서 ','를 이용해 방문처리를 해주려고 했다. 그렇게 하니까 불이 먼저 번짐 처리 되었을 때, 방문처리를 동시에 할 수가 없어서 조금 난감했다. 그래서 방문 체크를 조금 느슨하게 했더니 바로 메모리 초과가 났다.

 물론 불인데 방문한 곳을 뜻하는 문자를 하나 더 지정했다면 해결할 수 있었을 거 같다. 하지만 직관적으로 짜는게 나중에 코딩 테스트나 사후 리뷰 때 유리한 부분이 있을 것 같아서 그냥 방문 행렬을 따로 만들어 이용했고 바로 통과했다. 뻔한 로직이지만 약간 신경을 쓴 부분이 있다면, 큐에다 불과 상근이의 위치를 모두 넣으며 처리하지 않고 불의 위치는 Set을 이용해 따로 관리했다. 그덕에 불의 번짐 처리를 할 때 따로 중복체크는 필요 없어졌다.

 

#include <iostream>

#include <queue>

#include <set>

#include <vector>

using namespace std;

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

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

vector<vector<char> > matrix;

vector<vector<bool> > isVisited;

int w, h;

int main() {

    cin.tie(nullptr);

    ios_base::sync_with_stdio(false);

    int T;

    cin >> T;

    for(int t=0; t<T; t++) {

        cin >> w >> h;

        matrix = vector<vector<char> >(h+2, vector<char>(w+2, 'E'));

        isVisited = vector<vector<bool> >(h+2, vector<bool>(w+2, false));

        set<pair<int, int> > fireSet;

        queue<pair<pair<int, int>, int> > q;

        for(int i=1; i<=h; i++) {

            for(int j=1; j<=w; j++) {

                cin >> matrix[i][j];

                if(matrix[i][j]=='@') {

                    q.push({{i, j}, 0});

                    matrix[i][j]=='.';

                }else if(matrix[i][j]=='*') {

                    fireSet.insert({i, j});

                }

            }

        }

        int time = 0;

        while(!q.empty()) {

            pair<int, int> cur = q.front().first;

            int curTime = q.front().second;

            q.pop();

            if(time==curTime) {

                set<pair<int, int> > newSet;

                for(auto fire: fireSet) {

                    for(int i=0; i<4; i++) {

                        int ny = fire.first+dy[i];

                        int nx = fire.second+dx[i];

                        if(matrix[ny][nx]=='.') {

                            matrix[ny][nx] = '*';

                            newSet.insert({ny, nx});

                        }

                    }

                }

                fireSet = newSet;

                time++;

            }

            if(matrix[cur.first][cur.second]=='E') {

                cout << curTime << "\n";

                time = -1;

                break;

            }else if(isVisited[cur.first][cur.second]) {

                continue;

            }

           

            isVisited[cur.first][cur.second] = true;

            for(int i=0; i<4; i++) {

                int ny = cur.first+dy[i];

                int nx = cur.second+dx[i];

                if(matrix[ny][nx]=='.' || matrix[ny][nx]=='E') {

                    q.push({{ny, nx}, curTime+1});

                }

            }

        }

        if(time != -1) {

            cout << "IMPOSSIBLE\n";

        }

    }

}

 

 

2. 안드로이드 공부

 Foreground Service와 ViewModel 간 통신을 위해 공부하고 있다. 아무래도 핵심로직이 될 거 같은데, 한창 시도하는 중이라 남길 말은 딱히 없다. 아직 생각대로 잘 구현되지 않는다.