[백준] 2667번 문제 풀이

문제

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

풀이

1. 1001 X 1001 크기의 배열에 입력을 받는데 입력받은 값이 1과 같다면 큐에 현재 i, j값을 쌍으로 묶어서 밀어 넣는다.

2. bfs함수를 실행한다

3. bfs함수가 끝나면 현재 배열에 0이 남았는지, 토마토가 며칠에 걸쳐서 전부 익었는지를 확인한다.

 

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

using namespace std;
int n, m;
int arr[1001][1001];
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { -1, 0, 1, 0 };
queue<pair<int, int> >q;

void bfs() {
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
            if (!arr[nx][ny]) {
                arr[nx][ny] = arr[x][y] + 1;
                q.push({ nx, ny });
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++){
            cin >> arr[i][j];
            if (arr[i][j] == 1) {
                q.push({ i, j });
            }
        }
    }
    bfs();
    int res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j] == 0) {
                cout << "-1\n";
                return 0;
            }
            res = max(res, arr[i][j]);
        }
    }
    cout << res - 1;
    return 0;
}

 

여담

이 문제는 몇일에 걸쳐서 풀었던 문제이다. 3일 정도 반복하면서 약간의 생각과 정답 풀이를 보니 어느 정도 BFS, DFS를 어떤 식으로 풀어야 하는지 약간의 감이 생긴 것 같다. 물론 아직도 문제를 보면 바로 문제를 풀기 위한 실마리를 찾지는 못한다.

그리고 이전에 제출해서 정답처리된(그래프 이론) 문제들도 며칠에 걸쳐서 계속 풀이를 보면서 아예 코드를 외우는 방식으로 진행을 했다. 그리고 처음에 그래프 이론 문제를 풀려고 봤던 영상을 또 봤는데 이제야 조금 이해가 되는 것 같다.

이제부터 모르는 게 있으면 바보같이 앉아서 고민하지 말고 그 부분에 대해서 다시 공부하는 게 현명하다고 생각한다.