BOJ 7576 - 토마토

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

7576번: 토마토

BFS 를 이용해 풀어야 하는 문제이다.

이 문제에서 주의해야될 것은

BFS 의 시작점과 날짜 계산에 대한 부분이다.

 

단순하게 1이 최초로 나온 좌표 부터 시작해서 쭉 BFS 를 돌리면 제대로 시간계산이 되지 않는다

동일한 날짜에 동시에 1인 여러 좌표에서 부터 시작해서 BFS 를 탐색해야 한다.

예를들면 예제 입력 3 에서

 

맨 처음 값이 1인 좌표는 (0,0) , (3,5) 이다. 

이 두 좌표에서 동시에 BFS 를 수행해서 날짜를 하나씩 증가해야 한다.

그 다음좌표에 +1 을 함으로써 날짜를 계산할 수 있다.

그 다음 좌표는 (1,0), (2,5) 이며 이 좌표에 들어갈 값은 2,

그 다음 좌표는 (2,0), (1,5) 이며 이 좌표에 들어갈 값은 3,

이런식으로 끝까지 가면 마지막 값이 7 이 된다.

 

처음 입력이 들어온 초기 입력값의 날짜는 0 이기 때문에

마지막 7 보다는 하나더 작아야 답에 맞출 수 있다.

그래서 마지막 값 - 1 을 해줘야 한다.

 

그리고 좌표 값 중 하나라도 0 인게 있으면 익지 않은 토마토가 있다는 뜻이므로, -1 을 출력하고,

 

또 다른 경우로 처음 부터 모두 1이 었으면 결국 마지막 값이 1이란 뜻이므로

1 - 1 을 해서 0을 출력하게 된다.

 

- c++

#include <iostream>
#include <queue>
#include <utility>
#define MAX 1001
 
using namespace std;
 
int M, N, answer;
int adj[MAX][MAX];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
queue<pair<int, int>> q;
 
void bfs() {
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int new_y = y + dy[i];
            int new_x = x + dx[i];
            if ((0 <= new_x && new_x < M) && (0 <= new_y && new_y < N) && adj[new_y][new_x] == 0) {
                adj[new_y][new_x] = adj[y][x] + 1;
                q.push({new_y, new_x});
            }
        }
    }
}
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
 
    cin >> M >> N;  // 가로 세로 입력 (입력이 가로,세로 인것은 각각 열의갯수, 행의 갯수를 의미함, x,y 가아니라 y,x 란뜻)
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> adj[i][j];
            if (adj[i][j] == 1) {
                q.push({i, j});  // 초기의 익은 토마토만 큐에 넣기 위함 (y,x) 를 넣음
            }
        }
    }
 
    bfs();
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (adj[i][j] == 0) {
                // 하나라도 익지 않았다면 익을수 없는 토마토 상자라는 의미
                cout << "-1" << '\n';
                return 0;
            }
 
            if (answer < adj[i][j]) {
                answer = adj[i][j];
            }
        }
    }
 
    // 토마토 배열의 값이 1부터 시작하므로 1을 빼야 맞음.
    cout << answer - 1 << '\n';
 
    return 0;
}

 

 

 

 

당연히 처음 부터 이런생각은 전혀 못했다.

문제를 접했을때, DFS, BFS 관련 문제겠거니는 생각을 했지만

답을 정확히 찾는 부분에 있어서는 상당히 많이 틀렸다.

아래 블로그 글이 이 문제를 풀고 이해하는데 있어서 상당한 도움이 되었다

https://jdselectron.tistory.com/55#comment8031192

[백준 7576, c++] 토마토(bfs)

 

 

 

 

 

 

 

 

 

어째 문제를 풀면 풀수록

내 스스로 맞추는게 늘어야 하는데

전혀 느는것 같은 느낌이 안든다

잘못 공부하고 있는건가