백준 7576번 토마토 파이썬, C++

리뷰

BFS를 사용하여 풀었다.

 

문제 풀이

1. 가로 세로의 범위를 변수 M, N 및 2차원 배열의 정보를 리스트로 입력받아 저장하고, 방향 리스트를 초기화 한다.
2. BFS를 실행하고 방문을 표시할 V리스트 및 현재 배열에 존재하는 1들을 큐에 모두 넣어주고 해당 좌표를 방문 처리
3. while루프를 실행하여 큐에 있는 좌표에서 4방향 중 방문하지 않았고 값이 0인 경우 방문처리 및 현재 좌표의 값에 1을 더한 값을 저장해준다, 그리고 큐에 다음 좌표를 추가
4. bfs가 종료된 후 리스트를 순회하며 최고값을 갱신해 주고 만약 0이 있을 경우 flag를 작동시킨다.
5. flag가 작동 되어 있을경우 출력값은 -1, 아닐 경우 최고값에서 1을 빼준 값을 출력해 준다.

 

참고 사항

최고값에서 1을 빼주는 이유는 1인 값에서 부터 시작해서 +1된 값을 할당해줬기 때문이다.

bfs가 끝나고도 0이 존재한 경우 익지 않은 토마토가 있다는 말이다.

bfs에서 while이 돌기 전에 1의 값을 모두 넣어줘야 예제 2번과 같은 경우에서 정확한 값을 출력할 수 있다.

 

정답 코드

파이썬 코드

from collections import deque

m, n = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(n)]
dist = [(1, 0), (-1, 0), (0, 1), (0, -1)]


def bfs(n, m, array):
    q = deque()
    v = [[False] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if lst[i][j] == 1:
                q.append((i, j))
                v[i][j] = True
    while q:
        x, y = q.popleft()
        for dx, dy in dist:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < n and 0 <= ny < m and not v[nx][ny] and array[nx][ny] == 0:
                v[nx][ny] = True
                array[nx][ny] = array[x][y] + 1
                q.append((nx, ny))


bfs(n, m, lst)
max_day = 0
done = True

for i in range(n):
    for j in range(m):
        if lst[i][j] == 0:
            done = False
        max_day = max(max_day, lst[i][j])

print(max_day - 1 if done else -1)

 

C++ 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int m, n;
vector<vector<int>> lst;
vector<pair<int, int>> dist = {
	{1, 0}, {-1, 0}, {0, 1}, {0, -1}
};

void bfs() {
	queue<pair<int, int>> q;
	vector<vector<bool>> v(n, vector<bool>(m, false));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (lst[i][j] == 1) {
				q.push({ i, j });
				v[i][j] = true;
			}
		}
	}
	while (!q.empty()) {
		pair<int, int> pos = q.front();
		int x = pos.first;
		int y = pos.second;
		q.pop();

		for (const pair<int, int> dir : dist) {
			int dx = dir.first;
			int dy = dir.second;
			int nx = x + dx;
			int ny = y + dy;
			if (0 <= nx && nx < n && 0 <= ny && ny < m && !v[nx][ny] && lst[nx][ny] == 0) {
				v[nx][ny] = true;
				lst[nx][ny] = lst[x][y] + 1;
				q.push({ nx, ny });
			}
		}
	}
}

int main() {
	cin >> m >> n;
	lst.resize(n, vector<int>(m));
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> lst[i][j];
		}
	}

	bfs();
	int max_day = 0;
	bool flag = true;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (lst[i][j] == 0) flag = false;
			max_day = max(max_day, lst[i][j]);
		}
	}

	if (flag) cout << max_day - 1;
	else cout << -1;
}