[백준 7576번] 토마토 (C++/Python)

 

문제풀이 아이디어

핵심 BFS를 사용하는 queue에 x,y,count값을 저장한다.

N,M이 바뀌어서 주어지니 board입력받을 때 유의하자.

C++ 풀이

#include <bits/stdc++.h>

using namespace std;
queue<pair<pair<int,int>,int>> q; // x,y, count
int board[1001][1001];
bool visited[1001][1001];
int dx[4] = {-1, 0 , 1, 0}; //시계방향 탐색 (상 , 우 , 하 , 좌)
int dy[4] = {0,1,0,-1};
int N,M;
int res=0;
void bfs(){
    while(!q.empty()){
        int x=q.front().first.first;  //row 좌표
        int y = q.front().first.second; // col 좌표
        int c = q.front().second; // 며칠째인지
        q.pop();
        res = max(res,c); // 최대 일수를 res에 저장.
        for(int a = 0; a<4; a++) // 시계방향 탐색시작.
        {
            int nx = x + dx[a];
            int ny = y + dy[a];
            if(nx <0 || nx > M-1 || ny <0 || ny >N-1) continue; //맵의 범위를 벗어나거나
            if(visited[nx][ny] ==true) continue; // 이미 방문한 곳은 패스
            if(board[nx][ny] ==0) { // 안익은 토마토가 있다면
                visited[nx][ny] =true; // 방문했다 표시하고
                board[nx][ny] = 1; // 이제 익을거니까 보드를 변경후에
                q.push({{nx,ny},c+1}); // 그곳의 좌표와, 1일을 더해서 저장한다.
            }
        }
    }
    
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    for(int i = 0 ; i<M; i++)
    {
        for(int j = 0 ; j<N; j++)
        {
            int tmp;
            cin >> tmp;
            board[i][j] = tmp;
            if(tmp ==1) { // 입력 받을 때 부터 익은 토마토의 위치와 날짜를 0으로 해서 입력
                visited[i][j] =1;
                q.push({{i,j},0});
            }
        }
    }
    bfs();
    for(int i = 0 ; i<M; i++)
    {
        for(int j = 0 ; j< N; j++)
        {
            if(board[i][j] ==0) { // bfs탐색 돌고왔는데도 0인 토마토가 있다면 -1출력하고 종료
                cout << "-1";
                return 0;
            }
        }
    }
    cout << res << endl;
}

 

Python 풀이

import sys
from collections import deque
input = sys.stdin.readline

N,M=list(map(int, input().split()))

board = [list(map(int,input().strip().split())) for _ in range(M)]
visited = [[ 0 for _ in range(N)] for _ in range(M)]
dq = deque();
res = 0
def bfs():
    global dq,visited, res
    
    dx = [-1,0,1,0]
    dy = [0,1,0,-1]
    for i in range(M):
        for j in range(N):
            if board[i][j] == 1:
                dq.append([i,j,0])
                visited[i][j] = 1
    while dq:
        x,y,c = dq.popleft()
        res = max(c, res)
        for a in range(4):
            nx = x + dx[a]
            ny = y + dy[a]
            if  0<=nx<M and 0<= ny <N and visited[nx][ny] ==0:
                if board[nx][ny] ==0:
                    dq.append([nx,ny,c+1])
                    board[nx][ny] = 1
                    visited[nx][ny] =1

bfs()
flag = True
for i in range(M):
    for j in range(N):
        if board[i][j] ==0:
            print('-1')
            flag = False
            break
    if flag==False: break
            
if flag:
    print(res)