백준/ Gold 4 문제 , 백준 파이썬 2636 , 치즈 [BFS]

백준/ Gold 5 문제 , 백준 파이썬 2636 , 치즈[BFS]

 

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

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

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

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

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

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

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


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


<덧붙일 말>
bfs 가 몇번 호출되고, 이전 값이 뭐였는지, 만약 치즈가 한 번에 녹는 경우까지 생각잘해서 풀자.

 

문제 출처

 

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

2636번: 치즈

 

 

 

풀이

 

1. 기본 세팅

 

1. 상하좌우 움직임

 

2. N, M 입력 받기

 

3. 한 번에 치즈가 녹는 경우 맨 처음 치즈 갯수를 출력해주어야 하므로 맨 처음 치즈 갯수 세주기

 

 

 

 

2. BFS

한 번 지나간 0은 재탐색을 방지하기 위해 visited 리스트를 선언하여 같이 체크해준다.

 

중요한 점.

 

치즈를 발견하여 0으로 바꾸는 경우는 이동하기 전 위치가 0 이어야한다.

 

그러므로 이동할 곳이 1인지 와 함께 이전 위치가 0인지를 같이 확인해주어야 한다.

 

 

이 bfs 함수를 한번 돌게 되면 테두리 부분의 치즈들만 녹게 되며 남은 치즈들을 카운트해줘서 return 해준다.

 

 

 

3. bfs 호출 및 retrun 값 처리

 

bfs를 호출하고 return 되는 값들은 answer 리스트에 저장한다. 

 

만약 return 값이 0이라면 다 녹은 상태이므로 answer 리스트에 값이 얼마나 들었는지 확인한다.

 

만약 answer 리스트에 값이 하나도 담기지 않았다면, bfs 한 번의 호출만으로 다 녹아버린 상태로 한 번에 녹았다는 출력과 함께 맨 처음 세주었던 초기 치즈값을 출력 시켜주어야 한다.

 

이외에는 answer 에 담긴 값들 갯수 + 1 이 치즈가 다 녹기위 해 필요한 시간이고

 

 

 

 

 

 

 

 

정답

 

from collections import deque

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

N,M=map(int,input().split())
MAP=[]
first=0
for i in range(N):
    MAP.append(list(map(int,input().split())))
    first+=MAP[i].count(1)  # 초기 치즈 갯수 세두기
    
def bfs(x,y):
    dq=deque()
    dq.append([x,y])
    visited=[[False]*M for _ in range(N)]
    while dq:
        X,Y=dq.popleft()
        for i in range(4):
            mx=X+vertical[i]
            my=Y+parallel[i]
            if 0<=mx<N and 0<=my<M:
                if visited[mx][my]==False:
                    if MAP[mx][my]==1 and MAP[X][Y]==0:
                            visited[mx][my]=True
                            MAP[mx][my]=0
                    elif MAP[mx][my]==0:
                        dq.append([mx,my])
                        visited[mx][my]=True
                        MAP[mx]
    cnt=0
    for i in range(N):  # 녹고 남은 치즈 세기
        cnt+=MAP[i].count(1)
    return cnt
    
answer=[]  # 줄어드는 치즈값 저장
while True:
    result=bfs(0,0)
    if result==0:  # 치즈가 다 녹았을 시
        if len(answer)>0:
            print(len(answer)+1)
            print(answer[-1])  # 이전 치즈 갯수 출력
            break
        else:  # 치즈가 한 번에 다 녹아버린 경우
            print(1)
            print(first)  # 맨 처음 치즈 갯수를 출력해주자.
            break
    else:
        answer.append(result)

 

 

추가 문제

 

만약 판 가장자리에도 치즈가 있는 경우가 주어진다면?

 

 

ex)

4 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

 

 

 

해당 코드 추가 작성.