[백준] 7576. 토마토 풀이

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

 

입력받은 값에서 1을 찾은 후 1에서부터 탐색해나가며 각 위치의 탐색 깊이를 저장해야하는 문제이다.

 

1이 여러개일 수 있기 때문에 각 1에 대해서 탐색을 진행해야하나 싶었지만 bfs탐색 중 큐에 1의 위치들을 한번에 넣고 돌리면 동시에 탐색이 가능해진다.

즉, 1의 위치마다 다시 탐색할 필요가 없어진다.

 

따라서 반복문으로 1의 위치를 큐에 집어넣은 후 탐색 중 값이 0인 부분이 있다면 바로 이전 탐색 값에 +1을 하여 저장하는 방식으로 깊이를 저장하였다.

 

최총적으로 탐색을 마친 후 값들 중에 0이 존재하면 모든 토마토가 익은 것이 아니므로 -1을 출력하고, 존재하지 않으면 값들 중 최대값을 출력하여서 문제를 해결하였다. (만약 값이 -1을 제외하고 1밖에 없다면 이미 모든 토마토가 익어있는 상태이므로 0을 출력한다.)

 

---

C

#include <stdio.h>
#define MaxSize 10000000

int l[1000][1000];
int d[2] = {-1, 1};

// Queue
typedef struct{
    int data[MaxSize];
    int len;
    int front;
    int rear;
} Queue;
void initQueue(Queue* q){
    q->len = 0;
    q->front = 0;
    q->rear = 0;
}
int popleft(Queue* q){
    if(q->len > 0){
        int res = q->data[q->front];
        q->front += 1;
        q->len -= 1;
        if(q->front == MaxSize) q->front = 0;
        return res;
    }
}
void append(Queue* q, int v){
    int idx = q->rear;
    q->data[idx] = v;
    q->rear += 1;
    q->len += 1;
    if(q->rear == MaxSize) q->rear = 0;
}

void BFS(int n, int m){
    Queue q;
    initQueue(&q);

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(l[i][j] == 1) {
                append(&q, i);
                append(&q, j);
            }
        }
    }

    while(q.len > 0){
        int v[2];
        v[0] = popleft(&q); // y
        v[1] = popleft(&q); // x

        for(int i = 0; i < 2; i++){
            if (v[0] + d[i] < 0 || v[0] + d[i] >= n) continue;
            if(l[v[0] + d[i]][v[1]] == 0){
                append(&q, v[0]+d[i]);
                append(&q, v[1]);
                l[v[0] + d[i]][v[1]] = l[v[0]][v[1]]+1;
            }
        }
        for(int i = 0; i < 2; i++){
            if (v[1] + d[i] < 0 || v[1] + d[i] >= m) continue;
            if(l[v[0]][v[1] + d[i]] == 0){
                append(&q, v[0]);
                append(&q, v[1]+d[i]);
                l[v[0]][v[1] + d[i]] = l[v[0]][v[1]]+1;
            }
        }
    }
}

int main() {
    int m, n; scanf("%d %d", &m, &n);

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++) scanf("%d", &l[i][j]);
    }
    BFS(n, m);

    int mx = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if (l[i][j] > mx) mx = l[i][j];
            if (l[i][j] == 0) {printf("-1"); return 0;}
        }
    }
    printf("%d", mx-1);
}

---

Python

from collections import deque

d = [-1, 1]
def bfs(tomato):
    q = deque()
    for i in tomato:
        q.append(i)

    while len(q) > 0:
        v = q.popleft() # v[0] -> y, v[1] -> x

        for i in range(2):
            if l[v[0] + d[i]][v[1]] == 0:
                q.append([v[0]+d[i], v[1]])
                l[v[0]+d[i]][v[1]] = l[v[0]][v[1]]+1
        for i in range(2):
            if l[v[0]][v[1] + d[i]] == 0:
                q.append([v[0], v[1]+d[i]])
                l[v[0]][v[1] + d[i]] = l[v[0]][v[1]]+1

m, n = map(int, input().split())
l = []
l.append([-1 for _ in range(m+2)])
for i in range(n):
    v = list(map(int, input().split()))
    v.insert(0, -1)
    v.append(-1)
    l.append(v)
l.append([-1 for _ in range(m+2)])

tomato = []
cnt = 0
for i in range(1, n+1):
    for j in range(1, m+1):
        if l[i][j] == 1:tomato.append([i, j])
bfs(tomato)

mx = 0
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if l[i][j] > mx: mx = l[i][j]
        if l[i][j] == 0: mx = 2000000
print(mx-1 if mx != 2000000 else -1)