[CLASS 3]백준 1012번 - 유기농 배추

1012번 : 유기농 배추

 

배추흰지렁이를 놓는다는 컨셉을 가지고 있는 아주~ 기초적인 그래프 탐색 문제이다. BFS, DFS중 어느 것을 써도 쉽게 풀 수 있다.

 

쉽게 풀 수 있을 터였으나..

 

 

이렇듯 많은 시행착오가 있었다.

 

먼저 BFS로 시작해 보았다.

 

내 코드(시간 초과):

import sys
from collections import deque
input = sys.stdin.readline

def findArea(M,N,K):
    farm = [[False]*M for _ in range(N)]
    for _ in range(K):
        X,Y = map(int,input().split())
        farm[Y][X] = True

    areaCount = 0
    queue = deque()
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]

    for y in range(N):
        for x in range(M):
            if farm[y][x]:
                areaCount += 1
                queue.append((x,y))
                while queue:
                    coord = queue.popleft()
                    tx = coord[0]
                    ty = coord[1]
                    farm[ty][tx] = False

                    for i in range(4):
                        newX = tx + dx[i]
                        newY = ty + dy[i]
                        if 0 <= newX < M and 0 <= newY < N and farm[newY][newX]:
                            queue.append((newX,newY))
                        
    return areaCount

for _ in range(int(input())):
    M,N,K = map(int,input().split())
    print(findArea(M,N,K))

 

열심히 작성하고 제출했지만 시간 초과 판정을  맞았다. 그래서 어디가 틀렸나 계속 고민하고 질문까지 올렸었는데, 결론은 큐에 집어넣을때 방문 처리(farm=False)를 해줘야 한다. 만약 상단의 코드처럼 큐에 서 뺄때 방문 처리를 해준다면, 동일한 좌표가 큐에 같이 들어갈 수 있기 때문이다. 그래서 무한 루프에 걸려 시간 초과를 맞은 듯 하다. 이 간단하고 중요한 것을 몰랐다니..

 

내 코드(BFS):

import sys
from collections import deque
input = sys.stdin.readline

# bfs
def findArea(M,N,K):
    farm = [[False]*M for _ in range(N)]
    for _ in range(K):
        X,Y = map(int,input().split())
        farm[Y][X] = True

    areaCount = 0
    queue = deque()
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]

    for y in range(N):
        for x in range(M):
            if farm[y][x]:
                areaCount += 1
                farm[y][x] = False
                queue.append((x,y))
                while queue:
                    coord = queue.popleft()
                    tx = coord[0]
                    ty = coord[1]

                    for i in range(4):
                        newX = tx + dx[i]
                        newY = ty + dy[i]
                        if 0 <= newX < M and 0 <= newY < N and farm[newY][newX]:
                            farm[newY][newX] = False
                            queue.append((newX,newY))
                        
    return areaCount
    
for _ in range(int(input())):
    M,N,K = map(int,input().split())
    print(findArea(M,N,K))

 

이렇게 넣을때 방문처리를 해주면 잘 작동한다.

 

DFS로 풀어도 상관없지만 재귀 함수는 안쓰는게 좋을 듯 하다. 파이썬의 최대 재귀 횟수는 기본 설정이라면 1000이고 백준 채점 서버에도 1000으로 고정되어 있는 것으로 알고 있다. 즉 스택을 사용해서 구현하는것이 좋을 것 같다.

 

내 코드(DFS):

import sys
from collections import deque
input = sys.stdin.readline

# dfs
def findArea(M,N,K):
    farm = [[False]*M for _ in range(N)]
    for _ in range(K):
        X,Y = map(int,input().split())
        farm[Y][X] = True

    areaCount = 0
    stack = []

    for y in range(N):
        for x in range(M):
            if farm[y][x]:
                areaCount += 1
                stack.append((x,y))
                while stack:
                    tx = stack[-1][0]
                    ty = stack[-1][1]
                    farm[ty][tx] = False
                    if tx < M-1 and farm[ty][tx+1]:
                        stack.append((tx+1,ty))
                        continue
                    if ty < N-1 and farm[ty+1][tx]:
                        stack.append((tx,ty+1))
                        continue
                    if tx > 0 and farm[ty][tx-1]:
                        stack.append((tx-1,ty))
                        continue
                    if ty > 0 and farm[ty-1][tx]:
                        stack.append((tx,ty-1))
                        continue
                    stack.pop()
    
    return areaCount
    
for _ in range(int(input())):
    M,N,K = map(int,input().split())
    print(findArea(M,N,K))

 

이렇게 구현했다. 나는 개인적으로 BFS가 더 깔끔하고 직관적인 것 같다.