[Python][C++] 7569번 토마토

문제

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

 

 

코드

1. Python

from collections import deque

# 보드와 방문 여부를 저장하는 배열 초기화
board = [[[0 for _ in range(100)] for _ in range(100)] for _ in range(100)]
visited = [[[0 for _ in range(100)] for _ in range(100)] for _ in range(100)]

def bfs(n, m, h):
    # 방향벡터 설정 (6방향)
    dx = [-1, 1, 0, 0, 0, 0]
    dy = [0, 0, -1, 1, 0, 0]
    dz = [0, 0, 0, 0, -1, 1]

    q = deque()

    # 익은 토마토의 위치를 큐에 삽입하고 방문 처리
    for k in range(h):
        for i in range(n):
            for j in range(m):
                if board[k][i][j] == 1:
                    q.append((k, i, j))
                    visited[k][i][j] = 1

    # BFS 탐색
    while q:
        z, x, y = q.popleft()

        for i in range(6):
            nz = z + dz[i]
            nx = x + dx[i]
            ny = y + dy[i]

            # 보드 범위를 벗어난 경우 무시
            if nz < 0 or nz >= h or nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue

            # 익지 않은 토마토가 아닌 경우나 이미 방문한 경우 무시
            if board[nz][nx][ny] != 0 or visited[nz][nx][ny] != 0:
                continue

            # 방문처리 및 큐에 삽입
            visited[nz][nx][ny] = visited[z][x][y] + 1
            board[nz][nx][ny] = 1
            q.append((nz, nx, ny))


if __name__ == "__main__":
    m, n, h = map(int, input().split())

    for k in range(h):
        for i in range(n):
            for j in range(m):
                board[k][i][j] = int(input())

    bfs(n, m, h)

    cnt = 0

    for k in range(h):
        for i in range(n):
            for j in range(m):
                cnt = max(cnt, visited[k][i][j])

                if board[k][i][j] == 0:
                    print(-1)
                    exit(0)

    print(cnt - 1)

 

2. C++

#include <iostream>
#include <queue>
#include <tuple>
using namespace std;

int board[100][100][100];  // 3차원 보드를 나타내는 배열
int visited[100][100][100] = {};  // 방문 여부와 최단 거리를 저장하는 배열

// BFS 함수 정의
void bfs(int n, int m, int h) {
    // 6방향(상하좌우, 앞뒤)으로의 이동을 나타내는 배열
    int dx[6] = {-1, 1, 0, 0, 0, 0};
    int dy[6] = {0, 0, -1, 1, 0, 0};
    int dz[6] = {0, 0, 0, 0, -1, 1};

    queue<tuple<int, int, int>> q;  // BFS 탐색을 위한 큐, 좌표를 저장 (z, x, y)

    // 초기 상태에서 익은 토마토(값이 1인 위치)를 큐에 추가하고 방문 처리
    for (int k = 0; k < h; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[k][i][j] == 1) {
                    q.push(make_tuple(k, i, j));
                    visited[k][i][j] = 1;  // 익은 토마토의 위치를 방문 처리
                }
            }
        }
    }

    // BFS 탐색 시작
    while (!q.empty()) {
        int z, x, y;
        tie(z, x, y) = q.front();  // 큐에서 현재 위치를 꺼내옴
        q.pop();

        // 6방향으로 인접한 위치를 탐색
        for (int i = 0; i < 6; i++) {
            int nz = z + dz[i];
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 인접한 위치가 보드 범위를 벗어나면 무시
            if (nz < 0 || nz >= h || nx < 0 || nx >= n || ny < 0 || ny >= m)
                continue;

            // 인접한 위치가 이미 익었거나 방문된 적이 있으면 무시
            if (board[nz][nx][ny] != 0 || visited[nz][nx][ny] != 0)
                continue;

            // 방문 처리와 함께 큐에 추가
            visited[nz][nx][ny] = visited[z][x][y] + 1;  // 현재 위치에서 +1
            board[nz][nx][ny] = 1;  // 토마토가 익음
            q.push(make_tuple(nz, nx, ny));
        }
    }
}

int main() {
    int n, m, h;  // n: 행, m: 열, h: 높이

    cin >> m >> n >> h;  // 보드의 크기 입력

    // 보드 상태 입력
    for (int k = 0; k < h; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> board[k][i][j];
            }
        }
    }

    bfs(n, m, h);  // BFS 탐색 시작

    int cnt = 0;  // 최단 시간을 계산하기 위한 변수

    // 모든 보드를 탐색하며 최대 방문 시간 계산 및 익지 않은 토마토가 있는지 확인
    for (int k = 0; k < h; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cnt = max(cnt, visited[k][i][j]);  // 최대 시간을 갱신

                if (board[k][i][j] == 0) {  // 익지 않은 토마토가 있으면
                    cout << -1;  // -1 출력하고 종료
                    return 0;
                }
            }
        }
    }

    cout << cnt - 1;  // 최단 시간 출력 (첫 번째 방문을 1로 초기화했으므로 1을 빼줌)

    return 0;
}

 

 

풀이 

1. 3차원 BFS 구현:
   • 일반적인 2차원 BFS와 달리, 이 문제는 3차원이므로 방향을 나타내는 벡터가 6개(위, 아래, 앞, 뒤, 왼쪽, 오른쪽) 필요함
   • BFS를 통해 토마토가 익는데 걸리는 날짜를 계산하며, 모든 익지 않은 토마토가 익을 때까지 반복
2. 초기 상태 설정:
   • 먼저, 모든 익은 토마토들의 위치를 큐에 넣고, BFS를 시작
3. 결과 도출:
   • BFS 탐색이 완료된 후, 3차원 배열을 순회하여 익지 않은 토마토(0)가 남아 있는지 확인
   • 남아있다면 -1을 출력하고, 모두 익었다면 그동안 걸린 날짜 중 최대값을 출력

 

 

https://ehdbs0903.tistory.com/entry/Algorithm-너비-우선-탐색-BFSBreadth-First-Search-알고리즘

[Algorithm] 너비 우선 탐색 / BFS(Breadth-First Search) 알고리즘