알고리즘/백준 문제풀이
[boj] 백준 11123 양 한마리... 양 두마리... python 풀이
감자156
2023. 8. 13. 13:00
반응형
문제
https://www.acmicpc.net/problem/11123
11123번: 양 한마리... 양 두마리...
얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!"
www.acmicpc.net
문제 풀이
섬의 갯수를 찾는 bfs
코드
import sys
input = sys.stdin.readline
import collections
def bfs(MAP):
visited = [[0 for _ in range(len(MAP[0]))] for _ in range(len(MAP))]
move = {(-1,0),(0,-1),(1,0),(0,1)}
total = 0
for i in range(len(MAP)):
for j in range(len(MAP[0])):
if MAP[i][j] == '#' and visited[i][j] == 0:
total += 1
# bfs
q = collections.deque()
q.append((i,j))
visited[i][j] = 1
while q:
cx, cy = q.popleft()
for tx, ty in move:
nx = tx + cx
ny = ty + cy
if 0<=nx<len(MAP) and 0<=ny<len(MAP[0]) and MAP[nx][ny] == '#' and visited[nx][ny] == 0:
q.append((nx,ny))
visited[nx][ny] = 1
return total
T = int(input().strip())
for _ in range(T):
H,W = map(int,input().split())
MAP = [input().strip() for _ in range(H)]
print(bfs(MAP))
반응형