[파이썬] 백준 1888 : 곰팡이 (골드3)

[파이썬] 백준 1888 : 곰팡이 (골드3)

1888번: 곰팡이

---

문제

---

풀이

0. 방향성 생각

• 곰팡이가 사방으로 퍼져나간다.
• 한 덩어리로 된 것을 판별하려면 각 군집별로 disjoint set을 사용하거나 BFS를 돌려서 개수를 카운트 해주는 방법이 있다.
• 본인은 후자로 풀이. 곰팡이 군집을 만날때마다 카운팅을 해줘서 1개가 되는 순간의 날짜를 출력

1. 입력

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(map(int,input())) for _ in range(h)]
dire = [(1,0),(0,1),(-1,0),(0,-1)]
inside = lambda x,y : 0<=x<w and 0<=y<h

• inside는 격자 내 들어오는지 확인하는 함수

2. 곰팡이 덩어리 개수 카운트

def bfs(x,y,n): # 곰팡이 덩어리 BFS
    visit[y][x] = True
    q = deque([(x,y)])
    while q:
        x,y = q.popleft()
        for dx,dy in dire:
            nx,ny = x+dx,y+dy
            if inside(nx,ny) and not visit[ny][nx] and arr[ny][nx]:
                visit[ny][nx] = True
                q.append((nx,ny))

def check(): # 곰팡이 덩어리 개수 세는 함수
    cnt = 0
    for i in range(h):
        for j in range(w):
            if arr[i][j] and not visit[i][j]:
                bfs(j,i,arr[i][j])
                cnt += 1
    return cnt

• BFS를 돌려서 곰팡이를 만나면 계속 큐에 추가
• check는 BFS를 돌리면서 덩어리가 몇개인지 카운트

3. 곰팡이 퍼짐 구현

def spread():
    narr = [[0]*w for _ in range(h)]
    for y in range(h):
        for x in range(w):
            speed = arr[y][x]
            narr[y][x] = max(narr[y][x],arr[y][x])
            if speed:
                for nx in range(x-speed,x+speed+1):
                    for ny in range(y-speed,y+speed+1):
                        if inside(nx,ny) and arr[ny][nx] < arr[y][x]:
                            narr[ny][nx] = max(narr[ny][nx],arr[y][x])
    return narr

• 특정 좌표 x,y를 기준으로 그 곰팡이의 속도 += speed 범위 내의 격자를 조사한다.
• 속도가 빠른 곰팡이가 퍼져서 속도가 느린 곰팡이에 영향을 주면 안된다.
• 속도가 느린 곰팡이도 동시에 퍼지므로 구현해야한다는 말
• 새로운 narr이라는 어레이를 만들고 업데이트는 narr쪽에 해준다.

4. 시뮬레이션

day = 0
visit = [[False]*w for _ in range(h)]
count = check()
while count > 1:
    visit = [[False]*w for _ in range(h)]
    arr = spread()
    count = check()
    day += 1
print(day)

• 시뮬레이션
• visit은 계속 초기화시켜줘야한다.

---

전체코드

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(map(int,input())) for _ in range(h)]
dire = [(1,0),(0,1),(-1,0),(0,-1)]
inside = lambda x,y : 0<=x<w and 0<=y<h

def bfs(x,y,n): # 곰팡이 덩어리 BFS
    visit[y][x] = True
    q = deque([(x,y)])
    while q:
        x,y = q.popleft()
        for dx,dy in dire:
            nx,ny = x+dx,y+dy
            if inside(nx,ny) and not visit[ny][nx] and arr[ny][nx]:
                visit[ny][nx] = True
                q.append((nx,ny))

def check(): # 곰팡이 덩어리 개수 세는 함수
    cnt = 0
    for i in range(h):
        for j in range(w):
            if arr[i][j] and not visit[i][j]:
                bfs(j,i,arr[i][j])
                cnt += 1
    return cnt      

def spread():
    narr = [[0]*w for _ in range(h)]
    for y in range(h):
        for x in range(w):
            speed = arr[y][x]
            narr[y][x] = max(narr[y][x],arr[y][x])
            if speed:
                for nx in range(x-speed,x+speed+1):
                    for ny in range(y-speed,y+speed+1):
                        if inside(nx,ny) and arr[ny][nx] < arr[y][x]:
                            narr[ny][nx] = max(narr[ny][nx],arr[y][x])
    return narr
                
day = 0
visit = [[False]*w for _ in range(h)]
count = check()
while count > 1:
    visit = [[False]*w for _ in range(h)]
    arr = spread()
    count = check()
    day += 1
print(day)

 

코멘트

.