[Python] 백준 1012 - 유기농 배추

2021. 11. 6. 13:47·IT/알고리즘
반응형

문제

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

 

1012번: 유기농 배추

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 

www.acmicpc.net

문제 해결방법

bfs 로 해결 가능

graph[y][x] == 1 인 곳에서 검색을 시작하여
인접한 부분을 모두 0으로 변경한 뒤에 count++

문제 풀이

import sys
from collections import deque

T = int(sys.stdin.readline().strip())
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for _ in range(T):
    M, N, K = map(int, sys.stdin.readline().strip().split())
    graph = [[0] * M for _ in range(N)]
    for _ in range(K):
        x, y = map(int, sys.stdin.readline().strip().split())
        graph[y][x] = 1


    def bfs(x, y):
        queue = deque()
        queue.append((x, y))
        graph[y][x] = 0

        while queue:
            x, y = queue.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or nx >= M or ny < 0 or ny >= N:
                    continue
                if graph[ny][nx] == 1:
                    graph[ny][nx] = 0
                    queue.append((nx, ny))
        return 1


    count = 0
    for i in range(M):
        for j in range(N):
            if graph[j][i] == 1:
                count += dfs(i, j)

    print(count)
728x90
반응형
저작자표시 비영리 변경금지 (새창열림)
'IT/알고리즘' 카테고리의 다른 글
  • [Python] 백준 11724 - 연결 요소의 개수
  • [Python] 백준 7576 - 토마토
  • [Python] 백준 2667 - 단지번호붙이기
  • 프로그래머스 - 가장 큰 정사각형 찾기
상쾌한기분
상쾌한기분
  • 상쾌한기분
    상쾌한기분
    상쾌한기분
  • 전체
    오늘
    어제
    • 분류 전체보기 (251)
      • Python (44)
        • Python (26)
        • Django (6)
        • Flask (4)
        • Open Source (6)
      • Kotlin & Java (5)
        • Spring (2)
        • 프로젝트 (1)
      • Go (11)
      • Database (24)
        • MySQL (21)
        • Redis (3)
      • Infrastructure (2)
        • CDC (4)
        • Kafka (5)
        • Prometheus (2)
        • Fluentd (11)
        • Docker (1)
        • Airflow (2)
        • VPN (2)
      • IT (26)
        • AI (9)
        • Langchain (8)
        • Web (18)
        • Git (8)
        • 리팩토링 (9)
        • Micro Service Architecture (8)
        • Clean Code (16)
        • Design Pattern (0)
        • 수학 (1)
        • 알고리즘 (14)
      • OS (14)
        • Centos (10)
        • Ubuntu (3)
        • Mac (1)
      • Search Engine (2)
        • ElasticSearch (1)
        • Lucene Solr (1)
      • PHP (2)
        • Laravel (1)
        • Codeigniter (1)
  • 블로그 메뉴

    • Github 방문
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    Langchain
    Redis
    http
    python
    prompt
    performance
    오블완
    파이썬
    Kafka
    Golang
    LLM
    docker
    CDC
    티스토리챌린지
    ollama
    fluentd
    MYSQL
    go
    백준
    git
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
상쾌한기분
[Python] 백준 1012 - 유기농 배추
상단으로

티스토리툴바