BOJ 7576 - 토마토(C++) / Team Fortune Drill Week1

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

문제를 푼 날짜: 2025. 04. 10

#bfs #graphs #graph_traversal #grid_graph #shortest_path

내 풀이

#include <iostream>
#include <queue>
#include <utility>

using namespace std;

const int MAX = 1000;
int box[MAX + 1][MAX + 1];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int M, N;
    cin >> M >> N;

    queue<pair<int, int>> q;
    int day = 0;

    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> box[i][j];
            if(box[i][j] == 1) q.push({i, j});
        }
    }

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++){
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            if(nextX >= 0 && nextX < N && nextY >=0 && nextY < M){
                if(box[nextX][nextY] == 0){
                    //cout << nextX << ' ' << nextY << '\n';
                    box[nextX][nextY] = box[x][y] + 1;
                    if(box[nextX][nextY] > day) day = box[nextX][nextY] - 1;

                    q.push({nextX, nextY});
                }
            }
        }
    }

    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            // 안 익은 토마토 존재하는 경우
            if(box[i][j] == 0){
                cout << -1;
                return 0;
            }
        }
    }

    cout << day;
    return 0;
}

---

✅ 내가 풀면서 느낀 점

1. 입력 처리 실수: M, N의 의미

• 문제에서 'M'은 가로, 'N'은 세로를 의미한다.
• 그런데 실수로 'M * N' 배열을 M행 N열로 잘못 처리함.
• 실제 행렬 구조에서는 'box[N][M]'이 되어야 함 (세로 N행, 가로 M열)

✅ 교훈: 문제에서 주어진 축의 의미를 끝까지 정확히 이해해야 한다. 행렬을 처리할 때는 행과 열의 순서를 절대 헷갈리지 말자!

---

2. 기본 로직은 맞았지만 결과가 안 나올 때

• BFS 탐색 로직 자체는 문제 없이 잘 구현되어 있었음.
• 그런데 1번의 실수 때문에 결과가 잘못 나왔음.
• 입력 처리부터 차근차근 디버깅을 하면서, 금방 오류를 찾을 수 있었음.

✅ 교훈: 실전 대회에서는 '코드가 맞는데 왜 안 되지?' 싶을 때, 가장 기본적인 부분부터 차근차근 점검하기!

---

💯 코드 클린업 & 개선 팁

1. day 계산은 BFS 후 전체 순회로 정리 가능

• BFS 내에서 max_day를 갱신해도 되지만,
• 모든 탐색 후 최댓값을 한 번에 구하는 방식도 가독성 좋음

2. 명확한 변수 네이밍

• int M, N;보다는 cols, rows; 혹은 width, height;가 직관적

int rows, cols;
cin >> cols >> rows;