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

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

1012번: 유기농 배추

 

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으로 바꿔서 더 효율적으로 풀 수 있는 문제였다.