알고리즘/백준 문제풀이

[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))
반응형