M'S Blog

M'S Blog

WWDC20 student challenge Winner!

백준 7576 - 토마토

최대 1 분 소요

문제

백준 7576 - 토마토 풀러가기

문제 분석

며칠이 지나면 토마토가 익는지 최소 일수 를 구하는 문제다. 따라서 bfs를 이용하여 풀 수 있다.

문제 풀이

  1. 전체 코드

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    #include <cstdio>
    #include <queue>
    #include <algorithm>
     
    using namespace std;
     
    int box[1000][1000];
    int day[1000][1000];
    int ripe_total = 0;
    int total = 0;
    int lastDay = 0;
     
    int dx[] = { 1,0,0,-1 };
    int dy[] = { 0,1,-1,0 };
     
    queue<pair<int, int>> q;
     
    int n, m;
     
    void bfs() {
        while (!q.empty()) {
            int cr = q.front().first;
            int cc = q.front().second;
            for (int k = 0; k < 4; k++) {
                int nr = cr + dy[k];
                int nc = cc + dx[k];
                if (0 <= nr && nr < n && 0 <= nc && nc < m) {
                    if (box[nr][nc] == 0 && day[nr][nc] == 0) {
                        ripe_total++;
                        q.push(make_pair(nr, nc));
                        day[nr][nc] = day[cr][cc] + 1;
                        if (lastDay < day[nr][nc]) {
                            lastDay = day[nr][nc];
                        }
                    }
                }
            }
            q.pop();
        }
    }
     
    int main() {
        scanf("%d %d", &m, &n);
     
        total = m * n;
     
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%d", &box[i][j]);
                if (box[i][j] == 1) {
                    q.push(make_pair(i, j));
                    ripe_total++;
                }
                if (box[i][j] == -1) {
                    total--;
                }
            }
        }
     
        bfs();
     
        if(ripe_total < total) {
            printf("-1");
        }
        else {
            printf("%d", lastDay);
        }
     
        return 0;
    }
    		cs
    • 13~14번째 : 안익은 토마토는 익은 토마토 상하좌우에 있으면, 그 다음날 익게 된다. 따라서, 상하좌우만 확인해서 익은 토마토가 있는지, 빈칸인지, 안익은 토마토가 있는지 파악하면 된다. dx, dy 배열을 통해 상하좌우 파악을 용이하게 해준다.

  2. bfs 함수

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    void bfs() {
        while (!q.empty()) {
            int cr = q.front().first;
            int cc = q.front().second;
            for (int k = 0; k < 4; k++) {
                int nr = cr + dy[k];
                int nc = cc + dx[k];
                if (0 <= nr && nr < n && 0 <= nc && nc < m) {
                    if (box[nr][nc] == 0 && day[nr][nc] == 0) {
                        ripe_total++;
                        q.push(make_pair(nr, nc));
                        day[nr][nc] = day[cr][cc] + 1;
                        if (lastDay < day[nr][nc]) {
                            lastDay = day[nr][nc];
                        }
                    }
                }
            }
            q.pop();
        }
    }
     
    		cs
    • 9번째 : box[다음행] [다음열] 이 0이고 day[다음 행] [다음 열]이면 아직 방문하지 않은 안 익은 토마토가 있다는 것이다.
    • 12번째 : 여기서는 방문 = 하루가 지난 것이므로 day[다음행] [다음열]에 하루를 추가 한다.
      • 13번째 : 최대 일 수를 구하기 위한 조건문

  3. main 함수

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    int main() {
        scanf("%d %d", &m, &n);
     
        total = m * n;
     
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%d", &box[i][j]);
                if (box[i][j] == 1) {
                    q.push(make_pair(i, j));
                    ripe_total++;
                }
                if (box[i][j] == -1) {
                    total--;
                }
            }
        }
     
        bfs();
     
        if(ripe_total < total) {
            printf("-1");
        }
        else {
            printf("%d", lastDay);
        }
     
        return 0;
    }
    		cs
    • 9번째 : 기존에 익은 토마토는 바로 큐에 넣어준다.
    • 13번째 : 후에 익은 토마토와 총 토마토의 개수를 비교하여, 다 익을 수 없는 상태인지 확인에 용이하기 위한 부분.

    연관 문제






아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

댓글남기기

참고