(백준) 1012번 유기농 배추

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

 

이 문제는 구역 구하기 문제로 dfs로 쉽게 구현 할 수 있는 문제이다.

 

DFS

DFS는 깊이 우선 탐색으로 이름만 들으면 아래로 깊이 있게 내려간다는 건가라고 생각할 수 있지만, 그게 아니라 한쪽 방향으로 끈질기게 

계속 파고 들어가는 탐색 방식을 말한다.

즉, 상,하,좌,우가 있을때 위로 이동했으면 또 다시 상,하,좌,우를 탐색하고 끝이 있을 때까지 쭉 이동하는 방식인 것이다.

만약 끝이 보일 경우 다시 이전단계로 돌아와서 다음 가능한 여부를 파악한다.

BFS는 그저 인접한 노드로만 이동하기 때문에 그 점에서 차이가 존재한다.

 

또한 DFS는 스택으로 구현하지만, 재귀함수를 사용한다면 더 간단하게 구현할 수 있다. 그래서 굳이 스택을 사용하지 않아도 된다.

 

import sys

#재귀 깊이를 제한: 배추밭의 크기가 50x50 = 2500이면 최악의 경우 2500번 이상 재귀를 호출해야 할 수 있는데
#파이썬의 경우 기본적으로 재귀함수는 1000번까지만 제한하기 때문에 늘려줄 필요가 있다.
sys.setrecursionlimit(10000)

T = int(input()) #테스트 케이스 입력

def dfs(x,y):
    #지정된 구역을 벗어났을 경우
    if x < 0 or x >= m or y < 0 or y >= n:
        return False
    #해당 구역에 배추가 있는 경우
    if field[y][x] == 1:
        field[y][x] = 0 #방문처리
        
        #재귀함수로 상하좌우 탐색
        dfs(x+1,y)
        dfs(x-1,y)
        dfs(x,y+1)
        dfs(x,y-1)
        return True
    #배추가 없는 경우    
    return False        

#입력 받기
for _ in range(T):
    m, n , k = map(int, input().split()) #배추 밭의 크기와 배추 개수 입력

    field = [[0] * m for _ in range(n)] # 가로 M, 세로 N 만큼의 0으로 초기화 된 배추밭 만들기

    for _ in range(k):
        X,Y = map(int, input().split())
        field[Y][X] = 1 #배추가 있는 곳을 1로 초기화

    result = 0
    for i in range(n):
        for j in range(m):
            if dfs(j,i):
                result +=1

    print(result)

 

이 코드에서 주의할점은 다음과 같다.

 

1.sys.setrecursionlimit(10000)을 설정한 이유는 파이썬의 기본 재귀함수 제한 범위는 1000까지인데 
문제의 경우 50x50의 배추밭에 모든 배추가 존재하는 경우 최악의 경우 재귀함수가 1000을 넘어갈 수 있기 때문이다.

2. 2차원 배열과 실제 x,y좌표계는 다르다.

이차원 배열은 [세로][가로]로 구성되어 있기 때문

접근할때 [j][i] 이렇게 반대로 접근해야하며, 우리가 생각하는 x,y좌표계와는 반대로 뒤집힌 형태의 좌표계가 구성이 된다.

허나, 문제를 풀때 상대적 위치는 같으므로 굳이 수정할 필요가 없었다.