토마토

백준 7576

내가 생각하는 방식과 BFS를 어떻게 섞어서 구현해야하나 애를 먹었다. 처음 BFS를 구현하는 거니 당연하다고 생각한다. 비슷한 문제를 많이 풀어봐야겠다.

방법1. BFS

---

from collections import deque

w , h = map(int, input().split())
tomato = [list(map(int, input().split())) for _ in range(h)]

queue = deque()
for i in range(h):
    for j in range(w):
        if tomato[i][j] == 1: #값이1인지점부터 시작해야하니까 1인 지점들의 위치 기억
            queue.append([i,j])
            
#상하좌우
di = [-1, 1, 0, 0]
dj = [0, 0, -1, 1]
def bfs():
    while queue:  
        # 큐에 저장한 인덱스(익은애)를 기준으로 상, 하, 좌, 우 값 바꿔주기
        i, j = queue.popleft()
        # 상하좌우 좌표
        # 주변의 값을 바꾸고(주변을 익히고)
        for k in range(4):
            ni = i + di[k]
            nj = j + dj[k]
            #범위 벗어나면 넘어가기
            if ni < 0 or ni >= h or nj < 0 or nj >= w:
                continue
            #비어있으면 넘어가기
            if tomato[ni][nj] == -1:
                continue
            if tomato[ni][nj] == 0:
                tomato[ni][nj] = tomato[i][j] + 1
                #주변이 이제 주인공이 되어 주변의 값을 바꿔주기 위해 인덱스 큐에 저장
                #익은애가 이제 주인공이 되어 주변을 익히기 위해 보인 인덱스 저장
                queue.append([ni,nj])
                
    #안익은애 있으면 -1리턴
    for a in range(h):
        for b in range(w):
            if tomato[a][b] == 0:
                return -1
    #토마토 리스트에서 가장 큰 값-1을 리턴
    return max(map(max, tomato))-1
               
print(bfs())
     

큐에 저장한 인덱스(익은 토마토)를 기준으로 상, 하, 좌, 우 값을 검사해 익지 않았으면 익음처리해준다.

• BFS는 큐를 이용하여 구현하는데 덱 라이브러리를 사용하면 유용하다.

• 2차원 리스트 입력받기
  tomato = [list(map(int, input().split())) for _ in range(h)]
  h행만큼의 리스트 안에 리스트를 만들어줄건데 입력받는 수가 여러개이고 이들을 빈칸으로 구별해서 받을거야.
  1 -1 0 0 0 0
  0 -1 0 0 0 0
  0 0 0 0 -1 0
  0 0 0 0 -1 1
  ->이런애들 입력받을 때 쓰인다.
• 2차원 리스트에서 최댓값을 찾고 싶을 땐,
  max(map(max, 리스트이름))을 사용하면 된다.
  참고
  
  

2차 BFS 코드

from collections import deque

w, h = map(int, input().split())
tomato = [list(map(int, input().split())) for _ in range(h)]

queue = deque()
for i in range(h):
    for j in range(w):
    	#1이면 큐에 담아준다
        if tomato[i][j] == 1:
            queue.append([i,j])

dx = [-1,1,0,0]
dy = [0,0,-1,1]
def bfs():
#위에서 큐에 값을 담았으므로 바로 while문 진행
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<h and 0<=ny<w and tomato[nx][ny]==0:
                tomato[nx][ny] = tomato[x][y]+1
                queue.append([nx,ny])
    day = 0
    for i in range(h):
        for j in range(w):
            if tomato[i][j] == 0:
                return -1
            elif tomato[i][j] > day:
                day = tomato[i][j]
    return day-1
   
#처음부터 익어있었던 토마토박스는 최댓값이 1이므로 day는 0으로 리턴받는다.
print(bfs())