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

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

7576번: 토마토

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

 

---

 

⊙ 문제 접근 과정

 

코드를 다 짰는데 계속 정답 값이 안 나와 애먹은 문제다.

BFS로 풀었다. 간단한 문제다.

map을 입력받고 1의 값이 들어가면 queue에 push 한다. 그리고 1이 들어간 값들을 BFS를 돌린다.

그리고 방문을 안 한 곳이 있다면 days변수에 -1값을 넣고 출력, 전부 했으면 정상적인 days값을 출력한다.

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <queue>

using namespace std;
#define MAX 1001

int N,M;
int days=-1;
bool flag = false;
int tomato[MAX][MAX];
int visited[MAX][MAX];
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
queue<pair<int,int>> q;

int main() {
    cin >> M >> N;

    for(int i=0;i<N;i++) {
        for(int j=0;j<M;j++) {
            cin >> tomato[i][j];
            visited[i][j]=-1;

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

    while(!q.empty()) {
        int a = q.front().first;
        int b = q.front().second;
        q.pop();
        for(int i=0;i<4;i++) {
            int na = a + dx[i];
            int nb = b + dy[i];
            if(na>=0 && nb >=0 && N >na && M >nb && visited[na][nb]==-1 && tomato[na][nb]==0) {
                q.push({na,nb});
                visited[na][nb]=visited[a][b]+1;
            }
        }
    }
    
    for(int i=0;i<N;i++) {
        for(int j=0;j<M;j++) {
            if(days<=visited[i][j]) {
                days=visited[i][j];
            }
            if(tomato[i][j]==0 && visited[i][j]==-1) {
                days=-1;
                flag=true;
                break;
            }
        }
        if(flag)
            break;
    }

    cout << days;
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!