백준/ Gold 3 문제 , 백준 파이썬 2638, 치즈 [BFS]

백준/ Gold 3 문제 , 백준 파이썬 2638, 치즈 [BFS]

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
방문횟수랑 기존 위치를 잘 체크해주자.

 

문제 출처

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

2638번: 치즈

 

 

풀이

 

1. 기본세팅

 

1. 상하좌우 이동 (vertical, parallel 변수 이용)

 

2. N,M 입력 받기

 

3. MAP에 리스트 저장

 

 

 

2. BFS

0,0 부터 시작해서 쭉 탐색한다.

 

이때 치즈가 bfs 호출 한번만으로 다 녹는 것을 방지하기 위해 1을 만났을때는 dq에 넣지 않는다. 

 

오직 다음 칸이 0일때만 dq에 넣어서 이동시킨다.

 

 

다음 칸이 1인데 첫 방문일 경우 visited 에 해당 위치를 1 증가시켜주고

 

만약 첫방문이 아니면서 visited가 1이라면 그 1 부분은 0으로 바꿔줘서 녹여준다.

 

 

 

3. bfs 호출 및 카운트

 

이후 dq를 다 돌았다면 겉 부분 치즈만 녹아 있을 것이다.

 

남아 있는 1의 갯수를 cnt해줘서 return 시키고 따로 time 변수를 둬서 이 bfs가 몇번 호출 되었는지 세준다.

 

만약 return 값이 0이라면 치즈가 다 녹은 것이니 time을 출력해주고 종료시킨다.

 

 

 

 

정답

 

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

vertical=[1,-1,0,0]
parallel=[0,0,1,-1]

N,M=map(int,input().split())
MAP=[]
for i in range(N):
    MAP.append(list(map(int,input().split())))


def bfs(x,y):
    visited=[[0 for _ in range(M)] for _ in range(N)]
    dq=deque()
    dq.append([x,y])
    while dq:
        X,Y=dq.popleft()
        visited[X][Y]=1
        for i in range(4):
            mx,my=X+vertical[i],Y+parallel[i]
            if 0<=mx<N and 0<=my<M and MAP[X][Y]==0:
                if MAP[mx][my]==1:
                    if visited[mx][my]==0:
                        visited[mx][my]+=1
                    elif visited[mx][my]==1:
                        MAP[mx][my]=0
                elif MAP[mx][my]==0 and visited[mx][my]==0:
                    dq.append([mx,my])
                    visited[mx][my]=1
    cnt=0
    for i in range(N):
        for j in range(M):
            if MAP[i][j]!=0:
                cnt+=1
    return cnt

time=0
while True:
    result=bfs(0,0)
    time+=1
    if result==0:
        print(time)
        break