[파이썬] 백준 7576,7579 : 토마토 (골드5)

[파이썬] 백준 7576 ,7579: 토마토 (골드5)

7576번: 토마토

---

문제

---

풀이

0. 방향성 생각

최단거리 문제라서 BFS로 접근. 마지막 출력하는 부분만 조심하면 별 다른 조건도 없다.

 

1. 입력

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

w,h = map(int,input().split())
arr = []
q = deque()
for i in range(h):
    s = list(map(int,input().split()))
    for j in range(w):
        if s[j]==1:
            q.append((j,i))
    arr.append(s)

가로 세로 받아주고 시작점인 1들의 좌표들을 큐에 추가

어레이를 다 만들고 탐색해도 되는데 받으면서 진행

2. BFS 함수 정의

step = [[1,-1,0,0],[0,0,1,-1]]
def bfs():
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + step[0][i]
            ny = y + step[1][i]
            if 0<=nx<w and 0<=ny<h :
                if arr[ny][nx] == 0 :
                    arr[ny][nx] = arr[y][x] + 1
                    q.append((nx,ny))
bfs()

함수 내부에서 쓸 상하좌우 방향을 위해 step을 정의해주고 탐색.

탐색 시 안익었으면 현재 arr 값 +1로 해주고 다음 탐색을 위해 큐에 추가.

 

3. 출력

day,fail = 0,False
for i in range(h):
    if 0 in arr[i] :
        print(-1)
        fail = True
        break
    if day < max(arr[i]) :
        day = max(arr[i])
        
if not fail :
    print(day-1)

탐색 시 0이 있으면 -1 출력하고 for문 탈출, fail이 True이므로 안익었으므로 출력하지 않음

탐색 시 모두 익었으면 1부터 시작했으므로 -1 해주기

---

전체 코드

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

w,h = map(int,input().split())
arr = []
q = deque()
for i in range(h):
    s = list(map(int,input().split()))
    for j in range(w):
        if s[j]==1:
            q.append((j,i))
    arr.append(s)

step = [[1,-1,0,0],[0,0,1,-1]]
def bfs():
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + step[0][i]
            ny = y + step[1][i]
            if 0<=nx<w and 0<=ny<h :
                if arr[ny][nx] == 0 :
                    arr[ny][nx] = arr[y][x] + 1
                    q.append((nx,ny))
bfs()

day,fail = 0,False
for i in range(h):
    if 0 in arr[i] :
        print(-1)
        fail = True
        break
    if day < max(arr[i]) :
        day = max(arr[i])
        
if not fail :
    print(day-1)

전형적인 2차원 배열 탐색문제라 골드5 좀 후한 느낌이 있다.

 

 

번외

이거는 7576 3차원 배열로 풀기. 2차원으로도 풀 수는 있다.

주의할점은 마지막 출력시 return처럼 한번에 탈출하는 형태가 아니라서 break 대신 exit(0) 써야한답니다..

이거까진 생각을 안해서 한 번 틀렸다.

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

w,h,d = map(int,input().split())
arr = []
q = deque()
for k in range(d):
    temp = []
    for i in range(h):
        s = list(map(int,input().split()))
        for j in range(w):
            if s[j]==1:
                q.append((j,i,k))
        temp.append(s)
    arr.append(temp)

step = [[1,-1,0,0,0,0],[0,0,1,-1,0,0],[0,0,0,0,1,-1]]
def bfs():
    while q:
        x,y,z = q.popleft()
        for i in range(6):
            nx = x + step[0][i]
            ny = y + step[1][i]
            nz = z + step[2][i]
            if 0<=nx<w and 0<=ny<h and 0<=nz<d:
                if arr[nz][ny][nx] == 0 :
                    arr[nz][ny][nx] = arr[z][y][x] + 1
                    q.append((nx,ny,nz))
bfs()

day,fail = 0,False
for k in range(d):
    for i in range(h):
        if 0 in arr[k][i] :
            print(-1)
            fail = True
            exit(0)
        if day < max(arr[k][i]) :
            day = max(arr[k][i])
        
if not fail :
    print(day-1)