[백준] 1012 유기농 배추(Python)

1. 생각 정리

• 전체 map에서 배추가 심어져 있는 위치를 입력받고, 몇 개의 지렁이가 필요한지 구하는 문제
• 지렁이는 인접한 배추로 이동할 수 있기 때문에 연결되어있는 배추 지역에는 지렁이가 하나만 있어도 됨
• 결국 전체 map에 0(배추x), 1(배추 o)로 입력을 받고 섬처럼 생긴 1 지역이 몇 개인지? 구하는 접근을 가지면 됨
• DFS와 BFS 둘 다 활용하여 풀어보자

 

2. BFS 시간초과 코드

• 한번 탐색한 부분은 다시 탐색하지 않게 전체 map과 같은 크기인 visited 리스트를 따로 만들어서 정보를 관리했더니 시간 초과가 떴다.

#bfs 시간초과
from collections import deque 
 
def bfs(start):
    q=deque()
    q.append(start)
    dir = [(-1,0),(1,0),(0,-1),(0,1)]
    while q:
        x,y = q.popleft()
        for dx, dy in dir:
            nx, ny = x+dx, y+dy
            if 0<=nx<n and 0<=ny<m and mapp[nx][ny] and mapp[nx][ny]==1:
                mapp[nx][ny] = 2
                q.append((nx, ny))
    
for _ in range(int(input())):
    m,n,k = map(int, input().split())
    mapp = [[0]*m for _ in range(n)]
    for _ in range(k):
        y,x = map(int, input().split())
        mapp[x][y] = 1
    result=0
    
    for i in range(n):
        for j in range(m):
            if mapp[i][j]==1:
                mapp[i][j]=2
                bfs((i,j))
                result+=1
    print(result)

 

3. BFS 정답 코드

• 따로 visited 리스트를 만들지 않고
• mapp에서 (배추 없는 영역: 0), (배추 있는데 이미 탐색한 영역: 2), (배추 있는데 아직 탐색하지 않은 영역: 1) 이렇게 숫자를 바꿔가며 탐색 정보를 관리

from collections import deque 
 
def bfs(start):
    q=deque()
    q.append(start)
    dir = [(-1,0),(1,0),(0,-1),(0,1)]
    while q:
        x,y = q.popleft()
        for dx, dy in dir:
            nx, ny = x+dx, y+dy
            if 0<=nx<n and 0<=ny<m and mapp[nx][ny] and mapp[nx][ny]==1:
                mapp[nx][ny] = 2
                q.append((nx, ny))
    
for _ in range(int(input())):
    m,n,k = map(int, input().split())
    mapp = [[0]*m for _ in range(n)]
    for _ in range(k):
        y,x = map(int, input().split())
        mapp[x][y] = 1
    result=0
    
    for i in range(n):
        for j in range(m):
            if mapp[i][j]==1:
                mapp[i][j]=2
                bfs((i,j))
                result+=1
    print(result)

 

4. DFS 정답 코드

• 단, recursionlimit을 늘려주지 않으면 RecursionError 발생

#dfs
import sys
sys.setrecursionlimit(100000)#이거 설정 안해주면 RecursionError
 
def dfs(x,y):
    visited[x][y] = True
    dir = [(-1,0),(1,0),(0,-1),(0,1)]
    for dx, dy in dir:
        nx, ny = x+dx, y+dy
        if 0<=nx<n and 0<=ny<m and mapp[nx][ny] and not visited[nx][ny]:
            dfs(nx, ny)
            
for _ in range(int(input())):
    m,n,k = map(int, input().split())
    mapp = [[0]*m for _ in range(n)]
    visited = [[False]*m for _ in range(n)]
    for _ in range(k):
        y,x = map(int, input().split())
        mapp[x][y] = 1
    result=0
    for i in range(n):
        for j in range(m):
            if mapp[i][j] and not visited[i][j]:
                dfs(i,j)
                result+=1
    print(result)