[백준(BOJ)] 7576번 토마토 C++

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

7576번: 토마토

 

어떤 문제인가?

입력된 그래프를 탐색해나가며 모든 토마토가 익는데 걸리는 최소 날짜를 출력하는 문제이다.

 

 

 

접근 방법

int tomato[1001][1001];
bool visited[1001][1001];
int n, m;

토마토 상자의 값을 저장할 이차원 배열과 방문 여부를 저장할 이차원 배열, n과 m을 선언해준다.

 

queue<pair<int, int>> q;

탐색에 필요한 큐를 선언해준다. 이때 x좌표와 y좌표를 저장해야 하니 pair를 사용해준다.

 

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

 

위 두 배열은 미로에서 한 좌표가 주어졌을 때 상, 하, 좌, 우로 이동하기 위한 배열이다.

 

 

cin >> m >> n;

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        cin >> tomato[i][j];

        if (tomato[i][j] == 1) {
            q.push({i, j});
        }
    }
}

m과 n을 입력받고 토마토 상자의 값을 입력받는다.

이때, 익은 토마토 라면 큐에 그 좌표를 추가해준다.

 

그래서 이 좌표부터 탐색을 시작해나갈 것이다.

bfs();

그리고 bfs를 시작한다.

 

왜 bfs를 사용했냐면, 익지 않은 좌표의 토마토가 익기 위한 날짜는 익은 토마토의 좌표로부터 익지 않은 토마토의 좌표에 도달하는 최단거

리이기 때문이다.

 

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 x2 = x + dx[i];
            int y2 = y + dy[i];

            if (x2 < 0 || y2 < 0 || x2 >= n || y2 >= m) {
                continue;
            }

            if (tomato[x2][y2] == 0 && !visited[x2][y2]) {
                visited[x2][y2] = true;
                tomato[x2][y2] = tomato[x][y] + 1;
                q.push({x2, y2});
            }
        }
    }
}

다른 bfs문제와 별다를 것이 없다.

익은 토마토의 x좌표와 y좌표를 상, 하, 좌, 우로 움직여가며 그래프를 탐색한다.

n*m 범위를 벗어나면 다음 반복으로 넘어간다.

그리고 만약 이동한 좌표의 값이 0(익지 않은 토마토)이고 방문되지 않았다면

방문처리를 해주고

이동한 좌표의 값을 익은 토마토의 x좌표와 y좌표에 저장되어 있는 값(익지 않은 토마토의 좌표에 도달하는 거리)에 + 1로 해준다.

 

 

이제는 모든 토마토가 익지 못하는 상황인지 파악하고 토마토가 모두 익는 최소 날짜를 출력해야 한다.

int maxNum = 0;

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (tomato[i][j] == 0) {
            cout << -1;
            return 0;
        }
        maxNum = max(maxNum, tomato[i][j]);
    }
}
cout << maxNum - 1;

반복문을 돌며 변경된 그래프를 탐색한다.

만약 어떤 좌표의 값이 0이라면 bfs를 실행했는데도 토마토가 익지 못한 것이므로 0을 출력하고 main함수를 종료한다.

 

그렇지 않다면, maxNum과 좌표의 값을 비교해 더 큰 값을 maxNum으로 할당해준다.

모든 반복이 끝난 후 maxNum를 출력해주면 끝!

 

무엇이 어려웠는가?

1. 탐색을 시작할 위치를 저장하는 방법을 찾는 것

전형적인 bfs의 틀에서 항상 bfs 함수 내에 큐를 선언하고 파라미터로 좌표값을 넘겨받아 (0, 0)부터 탐색을 시작했다.

하지만 이 문젠 탐색을 시작할 위치가 경우마다 달라서 어렵게 느껴졌다.

1인 좌표부터 시작을 해야 하므로 큐를 전역으로 빼주어 입력단계에서 처리해 줄 수 있었다.

 

2. x좌표 y좌표와 이차원 배열의 i, j가 갑자기 너무 헷갈리기 시작했다.

통일이 안된 느낌이랄까? 그래서 i-x, j-y의 관계로 다시 설정했다.

 

 

3. 이건 또 문제를 제대로 안 읽어서 그런 건데...

문제의 "만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고" 이 부분을 처리할 때

왜 0에 꽂힌 건지 0이 익은 토마토라 생각하고 flag변수를 두어 모두 0으로 입력됐는지 예외처리를 했다.. 

틀렸습니다가 뜨고,,, 문제를 다시 읽고 현타...

 

배운 점

내가 자주했던 방식에 생각을 가두지 말자.. 

당연한 소리인데.. 문제마다 어떻게 방식이 같을 수가 있나... 운으로 비슷한 방식의 문제를 풀었던 것이다..

 

****문제를 꼼꼼하게 읽자****

어려운 부분보다 사소한 실수에서 발생하는 실수가 너무 괴롭다ㅠㅠ..

 

 

전체 코드

https://github.com/farmJun/Algorithm_BOJ_PS/blob/main/DFS%EC%99%80%20BFS/7562.cpp

GitHub - farmJun/Algorithm_BOJ_PS: 백준 알고리즘 문제풀이 기록 레포짓입니다.