백준 : 토마토(7576) with 파이썬

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

7576번: 토마토

문제

이 문제의 핵심만 집어보자.

N x M의 상자에 토마토가 있다. ( N = 가로, M = 세로 || 2 <= M, N <= 1000)

익지 않은 토마토 : 0

익은 토마토 : 1

토마토 없는 칸 : -1

0인 토마토를 1인 익은 상태로 변환시키면 된다.

0이 1이 되는 방범은 오른쪽, 왼쪽, 위, 아래로 하루마다 전염시킨다.

즉, 오른쪽, 왼쪽, 위, 아래가 -1로 막혀 있다면 0인 토마토는 1이 될 수 없음을 의미한다.

따라서 우리는 토마토가 없는 칸 -1을 벽이라고 생각하고 코드를 짜면 된다.

 

문제풀이

위에서 정의한 내용을 문제의 예제 입출력을 통해서 분석해 보려한다.

총 4가지의 예제중 예제 입력1, 예제 입력4를 직관적으로 보기위해 그림으로 표현해보았다.

예제 입력 1 복사

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

예제 출력 1 복사

8

문제의 내용대로 1의 오른쪽, 왼쪽, 위, 아래 토마토를 1로 바꾸었더니 result에 8이라는 결과값이 담겼다.

 

다음은 예제입출력 4를 보자

예제 입력 4 복사

5 5
-1 1 0 0 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 0 0 0 0

예제 출력 4 복사

14

마찬가지로 1의 오른쪽, 왼쪽, 위, 아래를 1로 전염시켰더니 result가 14라는 결과가 나왔다.

 

그럼 이제 코드를 살펴보자.

from collections import deque

m,n = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(n)]

q = deque([])

dx = [-1, 1, 0, 0]

dy = [0, 0, -1, 1]

for i in range(n):

      for j in range(m):

            if graph[i][j] == 1:

               q.append([i,j])

while q:

          x, y = q.popleft()

          for i in range(4):

                nx = x + dx[i]

                ny = y + dy[i]

                if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0:

                   graph[nx][ny] = graph[x][y] + 1

                   q.append([nx,ny])

result = 0

for i in graph:

      for j in i:

            if j == 0:

               print(-1)

               exit(0)

       result = max(result, max(i))

print(result - 1)

 

from collections

collections 모듈은 파이썬 표준 라이브러리에 포함된 모듈 중 하나로, 다양한 데이터 구조를 제공하여 데이터를 보다 효율적으로 관리하고 처리할 수 있도록 도와주는 도구들을 제공합니다. 

 

 import deque

deque는 큐(Queue)와 스택(Stack)의 기능을 모두 가진 자료 구조입니다. 큐와 스택은 데이터를 관리하는 방식이 다른데, 큐는 선입선출(FIFO, First-In-First-Out) 원칙에 따라 데이터를 처리하고, 스택은 후입선출(LIFO, Last-In-First-Out) 원칙에 따라 데이터를 처리합니다. 

deque 이용예시)

append(item): deque의 오른쪽 끝에 항목을 추가합니다.

pop(): deque의 오른쪽 끝에서 항목을 제거하고 반환합니다.

popleft(): deque의 왼쪽 끝에서 항목을 제거하고 반환합니다.

----------------------------------------------------------------------------------------------------------------

m,n = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(n)]

열, 행을 입력받고 토마토의 상태를 저장합니다.

 

split(): 입력받은 문자열을 공백을 기준으로 나누어 리스트로 변환하는 메서드입니다.

map() 함수는 첫 번째 인자로 주어진 함수를 두 번째 인자로 주어진 반복 가능한 객체의 모든 요소에 적용하여 새로운 리스트를 생성합니다

graph에 입력받은 열과 행을 2차원 리스트로 저장합니다.

 

q = deque([])

dx = [-1, 1, 0, 0]

dy = [0, 0, -1, 1]

빈 리스트 q를 생성합니다.

dx와 dy는 2차원 그리드에서 네 가지 주변 방향[상, 하, 좌, 우]을 표현하는 리스트입니다. 

따라서 dx = 상하, dy = 좌우를 의미하고 있습니다.

for i in range(n):

      for j in range(m):

           if graph[i][j] == 1:

               q.append([i,j]) 

입력받은 2차원 리스트n,m(행, 열)에서 1이 있는지 찾고 있다면 q에 추가합니다.

while q:

          x, y = q.popleft()

          for i in range(4):

               nx = x + dx[i]

               ny = y + dy[i]

               if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0:

                  graph[nx][ny] = graph[x][y] + 1

                  q.append([nx,ny])

위 코드는 BFS 방식입니다.

 q의 맨 왼쪽에 있는 노드를 가져와 x와 y에 할당합니다.

for문을 사용해서 상,하,좌,우를 검사합니다.

nx, ny는 현재위치에서 다음위치로 이동할 곳을 계산하기 위해 정의한 변수입니다.

if 조건문을 생성하고 새로운 위치 (nx, ny)가 그래프의 범위 내에 있고, 아직 방문하지 않은 빈 칸(값이 0인 칸)인 경우 graph에 1을 더해서 토마토가 익은 상태 -> 1로 만딘뒤 q에 저장합니다.

result = 0

for i in graph:

     for j in i:

          if j == 0:

             print(-1)

             exit(0)

      result = max(result, max(i))

몇일이 지났는지 결과값을 담을 변수 result를 선언합니다.

for문으로 모든 행과 열을 조사합니다.

if 조건문을 생성하여 익지않은 토마토(0)을 있다면 -1을 출력하고 종료시킵니다.

익지않은 토마토(0)이 없다면 result에 최댓값 i를 저장합니다.

print(result - 1)

result - 1을 하는 이유는 BFS(while)문을 돌릴 때 익은 토마토(1)부터 +1 했으므로 최종적으로 -1을 해줍니다.