백준 알고리즘 7576 (토마토) - C++, Python

[문제] 백준 알고리즘 7576 (토마토)

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

7576번: 토마토

 

상자의 크기 N, M이 주어지고, Map이 주어진다.

1은 토마토, 0은 안익은 토마토, -1는 빈공간이다.

익은 토마토는 상하좌우의 안익은 토마토에게 영향을 준다. 

며칠이면 모든 토마토가 익게 되는지를 출력하는 문제이다.

 

[문제 해결]

1. BFS를 위해 queue와 while문, visited(방문 여부)를 사용한다.

2. dx, dy를 이용해 queue에서 나온 현재 지점의 상하좌우를 탐색한다.

3. 안익은 토마토이고, 방문하지 않았으면 이전의 값을 누적한다.

4. 그 지점을 queue에 push한다.

5. Map을 검사하면서 max값-1을 출력하고, 0이 존재하면 -1 출력한다. 

 

[C++]

#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
int n, m;
const int MAX = 1001;
int map[MAX][MAX];
bool visited[MAX][MAX];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };
queue< pair<int, int> > q;

void solve_bfs() {
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (0 <= nx && nx < m && 0 <= ny && ny < n) {
				if (map[nx][ny] == 0 && !visited[nx][ny]) {
					visited[nx][ny] = 1;
					map[nx][ny] = map[x][y] + 1;
					q.push({ nx, ny });
				}
			}
		}
	}
}

int main() {
	memset(map, 0, sizeof(map));
	memset(visited, 0, sizeof(visited));
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &map[i][j]);
		}
	}	
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 1 && !visited[i][j]) {
				visited[i][j] = 1;
				q.push({ i, j });
			}
		}
	}
	solve_bfs();

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

 

[Python]

from collections import deque
import sys
n = int(sys.stdin.readline())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dx = [0, 1, 1]  # 가로, 세로, 대각선
dy = [1, 0, 1]  # 가로, 세로, 대각선
q = deque()

def solve_bfs(x, y, d):
    cnt = 0
    q.append((x, y, d))
    while q:
        x, y, d = q.popleft()
        if x == n-1 and y == n-1:
            cnt += 1
        for i in range(3):
            nx, ny, nd = x + dx[i], y + dy[i], i
            if nx < n and ny < n and nd + d != 1:
                if not board[nx][ny]:
                    if i == 2:
                        if not board[nx-1][ny] and not board[nx][ny-1]:
                            q.append((nx, ny, nd))
                    else:
                        q.append((nx, ny, nd))
    return cnt

print(solve_bfs(0, 1, 0))