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

문제

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

 

 

 

코드

1. Python

from collections import deque

# m과 n을 입력받음 (m: 가로 길이, n: 세로 길이)
m, n = map(int, input().split())

# 보드 초기화
board = []

# 보드 상태를 입력받아 2차원 리스트로 저장
for _ in range(n):
    board.append(list(map(int, input().split())))

# 방향 벡터 설정 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS를 위한 큐 초기화
q = deque()

# 익은 토마토(값이 1인 칸)의 위치를 모두 큐에 추가
for i in range(n):
    for j in range(m):
        if board[i][j] == 1:
            q.append((i, j))

# BFS 시작
while q:
    x, y = q.popleft()  # 큐에서 현재 위치를 꺼냄

    # 현재 위치에서 상, 하, 좌, 우로 인접한 칸을 확인
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        # 인접한 칸이 보드의 범위를 벗어나면 무시
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue

        # 인접한 칸이 익지 않은 토마토(값이 0)인 경우
        if board[nx][ny] == 0:
            q.append((nx, ny))  # 큐에 추가
            board[nx][ny] = board[x][y] + 1  # 익히고, 걸린 일수를 현재 위치의 일수 + 1로 저장

# 모든 칸을 검사하여 결과 계산
days = 0  # 걸린 일수를 저장할 변수

for i in range(n):
    for j in range(m):
        # 만약 익지 않은 토마토(값이 0)가 하나라도 남아있으면 -1 출력 후 종료
        if board[i][j] == 0:
            print(-1)
            exit()  # return 대신 exit() 사용하여 프로그램 종료
        # 모든 칸 중 최대 일수를 계산
        days = max(days, board[i][j])

# 초기 상태가 1인 칸이 걸린 시간이므로 1을 빼서 출력
print(days - 1)

 

2. C++

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

int main() {
    int m, n;

    cin >> m >> n;  // m: 열의 수, n: 행의 수 입력

    int board[1000][1000];  // 2차원 보드를 나타내는 배열

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

    // 상하좌우 4방향을 나타내는 배열
    int dx[4] = { -1, 1, 0, 0 };
    int dy[4] = { 0, 0, -1, 1 };

    int x, y;  // 현재 위치를 나타내는 변수
    queue<pair<int, int>> q;  // BFS를 위한 큐

    // 익은 토마토(값이 1인 위치)를 큐에 추가
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j] == 1)
                q.push(make_pair(i, j));
        }
    }

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

        // 상하좌우 4방향으로 인접한 위치를 탐색
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];  // 새로운 x 위치
            int ny = y + dy[i];  // 새로운 y 위치

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

            // 인접한 위치에 익지 않은 토마토(값이 0)라면
            if (board[nx][ny] == 0) {
                q.push(make_pair(nx, ny));  // 그 위치를 큐에 추가
                board[nx][ny] = board[x][y] + 1;  // 현재 위치에서 +1로 익음 처리
            }
        }
    }

    int days = 0;  // 모든 토마토가 익는 데 걸리는 일수를 저장할 변수

    // 모든 보드를 탐색하여 익지 않은 토마토가 있는지 확인
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j] == 0) {  // 익지 않은 토마토가 있으면
                cout << -1;  // -1 출력하고 종료
                return 0;
            }
            days = max(days, board[i][j]);  // 최대 일수를 갱신
        }
    }

    cout << days - 1;  // 처음 시작을 1로 초기화했으므로 1을 빼줌

    return 0;
}

 

 

풀이 

7569번 토마토 문제를 2차원으로 바꾼 문제

 

1. BFS 구현:
   • 큐에는 현재 익은 토마토의 위치를 저장하고, 이 위치에서 인접한 토마토들을 익히는 작업을 반복
   • 4가지 방향(위, 아래, 왼쪽, 오른쪽)을 탐색하면서 익지 않은 토마토가 있으면 해당 토마토를 익히고 큐에 삽입
2. 초기 상태 설정:
   • 먼저, 모든 익은 토마토(1)의 위치를 큐에 넣고, BFS 시작
3. 결과 도출:
   • BFS 탐색이 완료된 후, 배열을 순회하며 익지 않은 토마토(0)가 남아 있는지 확인
   • 남아 있다면 -1을 출력하고, 모두 익었다면 BFS 과정에서 기록한 날짜 중 가장 큰 값을 출력

 

 

https://ehdbs0903.tistory.com/entry/PythonC-7569번-토마토

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

 

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

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