본문 바로가기
🔅코딩테스트 공부🔅/❗백준

[백준] 1012번 유기농 배추(with python)

by 윤무무 2023. 2. 8.

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

 

1012번: 유기농 배추

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

www.acmicpc.net

 

1. 내가 작성한 코드

 

1. BFS풀이

from collections import deque

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

    dx = [-1,1,0,0]
    dy = [0,0,-1,1]

    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if nx < 0 or ny < 0 or nx >=n or ny >=m:
        continue
      if matrix[nx][ny] == 0:
        continue
      if matrix[nx][ny] == 1:
        queue.append((nx,ny))
        matrix[nx][ny] = 0


t = int(input())

for i in range(t):
  cnt = 0
  m,n,k = map(int, input().split())

  matrix = [[0] * m for i in range(n)]

  for i in range(k):
    m,n = map(int, input().split())
    matrix[n][m] = 1 ###고침

  for i in range(n):
    for j in range(m):
      if matrix[i][j] == 1: 
        cnt += 1
        bfs(matrix, i, j)

  print(cnt)

 

+

 

2. DFS풀이 

import sys

sys.setrecursionlimit(1000000)

def dfs(x,y):
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < 0 or ny < 0 or nx>=b or ny>=a:
            continue

        if maps[nx][ny] == 1:
            maps[nx][ny] = 0
            dfs(nx,ny)

    return True

t = int(input())

for _ in range(t):
    cnt = 0
    a,b,c = map(int, input().split()) #a가로 b세로 c배추
    maps = [[0] * a for _ in range(b)]


    for _ in range(c):
        d,e = map(int, input().split())
        maps[e][d] = 1

    for i in range(b):
        for j in range(a):
            if maps[i][j] == 1:
                maps[i][j] = 0
                dfs(i,j)
                cnt+=1
    print(cnt)

 

메모

처음에 visit라는 2차원 배열을 할당해서 방문 여부를 확인했으나,

 

그냥 1을 0으로 바꿔서 더 효율적으로 풀 수 있는 문제였다.

댓글