[Python/BOJ] 백준 7576 토마토(BFS)

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

7576번: 토마토

 

 

 

 

 

 

백준의 BFS 문제의 정석!!!!

 

 

🐾 20221024

 

 

 

 

💻 c++로는 여러번 풀었지만 파이썬으로는 처음 풀어본다. 

 

<코드>

from collections import deque
dx = [1,0,-1,0]
dy = [0,1,0,-1]
m,n = map(int, input().split())
arr = [list(map(int,input().split()))for _ in range(n)]

queue = deque()
for i in range(n) :
    for j in range(m) :
        if arr[i][j]==1 :
            queue.append([i,j])

def bfs() :
    while queue: 
        x,y =queue.popleft()
        for i in range(4) :
            nx ,ny = x+dx[i], y +dy[i]
            if 0<=nx<n and 0<=ny<m and arr[nx][ny]==0 :
                arr[nx][ny] = arr[x][y]+1
                queue.append([nx,ny])

bfs()
result = 0
for i in arr :
    for j in i :
        if j == 0 : 
            print(-1)
            exit(0)
    result = max(result,max(i))

print(result-1)

 

 

여기서 새롭게 알게된 코드 2부분이 있다.

 

 

 

1. 띄어쓰기로 구분된 이차원리스트를 입력받기

 

arr = list(map(int, input().split()))

-> 일단 이렇게 띄어쓰기로 구분된 숫자를 입력받아 정수형 리스트로 만들어주는 코드는 알고있었다.

 

이를 이차원 리스트로 받으려면 이것을 for문을 통해 반복시키고 리스트화 하면된다.

 

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

여기서 for✅_ ✅in 을 띄어쓰기 해주어야한다.

 

 

2. 이차원 리스트를 돌면서 0의 여부를 확인하고 가장 큰 값 확인하기

 

 

for i in arr :
    for j in i :
        if j == 0 : 
            print(-1)
            exit(0)
    result = max(result,max(i))

 

이해를 돕기위해 그림을 그려보았다.

 

arr는 n개의 리스트로 이루어져있다. 

그 각각의 리스트가 i 가 되고 

i 에서 각각의 문자가 j 가 되어 j에 0이 있는지 확인하고

하나의 i가 끝날때 max를 이용해 가장 큰 수를 구한다. 

 

 

 

🔑 그래서 어떻게 푸는데(정리)?

 

1. 2차원 리스트를 잘 만든다.

 

2. 2중 for문을 통해 1이 들어온 좌표를 덱에 넣는다.

 

3. dx , dy를 이용해 다음 x,y좌표를 구하고 범위에 맞는지, 방문 한적이 있는지 여부를 확인한다.

 

4. 확인 결과 내부에 있으며, 방문한적이 없다면 덱에 넣는다.

 

5. 덱이 빌 때까지 계속 반복한다.

 

6. 2차원 리스트를 돌면서 0이 있다면 -1을 출력하고 아니라면 최댓값을 구해 -1하여 출력한다.

(토마토가 처음 1이였고 여기에서 1씩 증가시켰으므로 )

 

 

 

 

 

 

---

 

이제 이 정도는 그냥 풀수있다ㅎㅎ

 

 

복습 코드 : 

from collections import deque 
dx = [0,1,0,-1]
dy = [1,0,-1,0]

if __name__=="__main__" :
    m,n = map(int,input().split())
    mp = [list(map(int,input().split())) for _ in range(n)]
    vis = [[-1]*m for _ in range(n)]
    
    q = deque()
    # 익은 토마토를 덱에 넣기
    for i in range(n) :
        for j in range(m) :
            if mp[i][j] == 1 :
                q.append([i,j])
                vis[i][j] = 0
    # 토마토 전염 
    while q :
        x,y = q.popleft()
        for dir in range(4) :
            nx,ny = dx[dir] + x , dy[dir] + y 
            if 0<=nx<n and 0<=ny<m and mp[nx][ny] == 0 and vis[nx][ny] == -1:
                q.append([nx,ny])
                vis[nx][ny] = vis[x][y] +1 
    
    # 만약 토마토가 비어있지 않은데 방문을 안했다?(익지 않았다.)
    # 그러면 안익은 토마토가 있는 것이므로 -1을 출력한 후 끝낸다. 
    for i in range(n) :
        for j in range(m) :
            if mp[i][j] != -1 and vis[i][j] == -1 :
                print(-1)
                exit(0)
    
    print(max(sum(vis,[])))

 

 

 

 

 

[참고]

 

 

https://jae04099.tistory.com/entry/%EB%B0%B1%EC%A4%80-7576-%ED%86%A0%EB%A7%88%ED%86%A0-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%ED%95%B4%EC%84%A4%ED%8F%AC%ED%95%A8?category=890007 

[백준] 7576: 토마토 (파이썬 / 해설포함)