[BoJ][Python] 1012 유기농 배추

목차

🫡 Overview

체감 난이도: ★☆☆☆☆

소요시간: 

문제 레벨: 실버2 / 문제 유형: BFS/DFS
풀이 상태: 스스로 해결
추후: 완벽 이해

 

---

문제 링크

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

 

나의 코드

from collections import deque

d_lst = [(-1,0),(0,+1),(1,0),(0,-1)] # 상 우 하 좌
def BFS(i,j):
    global visited
    q = deque()
    visited[i][j] = True
    q.append((i,j))
    # i,j의 인접한 배추들에 대해서 방문 처리를 해준다.
    while q:
        x,y = q.popleft()
        for dx,dy in d_lst:
            nx, ny = x+dx, y+dy
            if nx< 0  or nx>=N or ny<0 or ny>=M:
                continue
            if not visited[nx][ny] and board[nx][ny] == 1:
                visited[nx][ny] = True
                q.append((nx,ny))

if __name__ == "__main__":
    T = int(input())
    for t in range(T):
        M, N, K = map(int, input().split()) # 열, 행, 배추 개수
        board = [[0]*M  for _ in range(N)] # 밭
        # 배추가 있는 곳을 표시!
        for _ in range(K):
            x,y = map(int, input().split())
            board[y][x] = 1 # 배추가 있음
        # BFS를 수행
        visited = [[False]*M  for _ in range(N)]
        ans = 0
        for i in range(N):
            for j in range(M):
                if not visited[i][j] and board[i][j] == 1: # 방문하지 않은 배추 그룹일 경우
                    BFS(i,j)
                    ans += 1
        print(ans)

 

 

---