[TIL] 24.02.06

1. 알고리즘 문제 해결

 

나이트의 이동(백준 7562):

 앞서 풀었던 BFS 문제들과 같다. 큐에 좌표 값 및 이동횟수를 집어넣고 BFS를 이용한다. 크게 어려울 거 없는 문제.

 

 

 

토마토(백준 7576):

 이것도 BFS 문제인데 관성적으로 풀다가 조금 헤맸다. 익은 토마토들의 위치를 저장해놨다가 각각에 대해 BFS를 하는 식으로 처리하려고 했다가 시간초과가 났다. 매번 모든 부분을 탐색하게 되지 않도록, 숙성에 걸리는 일 수를 업데이트 해주며 나름 pruning을 했음에도 그랬다. 생각을 바꿔서 처음부터 큐에 모든 익은 토마토의 위치를 넣어두고 시작하고서야 해결할 수 있었다. 시작할 때 큐에 꼭 원소를 하나만 넣고 시작할 필요는 없는데, 생각이 갇혀 바로 떠올리지 못한게 아쉬웠다.

 

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

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

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

int n, m;

bool isValid(int y, int x) {

    return y>=0&&y<n&&x>=0&&x<m;

}

int main() {

    cin.tie(nullptr);

    ios_base::sync_with_stdio(false);

    cin >> m >> n;

    vector<vector<int> > matrix(n, vector<int>(m));

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

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

        for(int j=0; j<m; j++) {

            cin >> matrix[i][j];

            if(matrix[i][j]==1) {

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

                matrix[i][j] = 0;

            }

        }

    }

    int result = 0;

    while(!q.empty()) {

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

        int curDay = q.front().second;

        q.pop();

        if(matrix[cur.first][cur.second]==1) continue;

        matrix[cur.first][cur.second] = 1;

       

        if(curDay>result) {

            result = curDay;

        }

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

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

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

            if(isValid(ny, nx) && matrix[ny][nx]==0) {

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

            }

        }

    }

   

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

        for(int j=0; j<m; j++) {

            if(matrix[i][j] == 0) {

                cout << "-1";

                return 0;

            }

        }

    }

   

    cout << result;

}