[백준 1012] 유기농 배추

백준 1012번: 유기농 배추

 

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

1012번: 유기농 배추

 

설명

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추 근처에 서식하며 해충을 잡아먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

 

1	1	0	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	1	1	0	0	0	1	1	1
0	0	0	0	1	0	0	1	1	1

 

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로 길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그다음 K 줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

 

출력

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

 

 

풀이 과정

BFS 사용

# 큐를 쓰기 위해 collections 모듈 가져오기 
# list 를 안 쓰고 deque를 쓰는 이유는 list의 pop은 O(n) 이지만 deque는 O(1) 의 복잡도를 가짐. 
from collections import deque 

def BFS(graph, 탐색_x, 탐색_y):
    queue = deque() # 큐 선언 
    queue.append( (탐색_x, 탐색_y) ) # 큐에 최초 그래프 시작점(최초 배추 만난 좌표) 삽입
    graph[탐색_y][탐색_x] = 0 # 탐색한 그래프는 0으로 변경하여 재탐색 막음

    # for 문으로 상하좌우를 탐색하기 위해 단위 좌표 선언 
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    # 큐에 값이 있는 동안 BFS 계속 시행 
    while queue:
        x, y = queue.popleft() # enqueue 해서 값 가져오기
        # 좌표 범위를 넘지 않는 상하좌우에 대해 1인 값(배추가 있는 곳)을 찾으면 큐에 넣어 계속 탐색 
        for i in range(4):
            인접_x = x + dx[i]
            인접_y = y + dy[i]
            
            # 좌표 범위를 넘지 않고 값이 1인 (배추가 있는) 좌표값에 대해 재탐색을 막고 큐에 넣음 
            if ( 0 <= 인접_x < M and 0 <= 인접_y < N and graph[인접_y][인접_x] == 1 ):
                graph[인접_y][인접_x] = 0
                queue.append( (인접_x, 인접_y) )
    return # 더이상 큐에 탐색할 값이 없으면 함수 종료 
    
T = int(input()) # 테스트 케이스 입력 

for _ in range(T):
    cnt = 0 # BFS 실행한 횟수 (=필요한 지렁이 개수) 기록용 변수 선언 
    M, N, K = map(int, input().split()) # 가로길이, 세로길이, 배추개수 입력 
    graph = [ [0] * M for _ in range(N) ] # 가로 M 세로 N의 2차원 배열 선언 

    # 배추 위치 입력 파트 
    for _ in range(K):
        배추_x, 배추_y = map(int, input().split()) # 배추 좌표를 입력받아서 
        graph[배추_y][배추_x] = 1 # 좌표에 배추를 1로 표시 ( 배열의 y가 먼저 오는 것에 주의)

    # 배추 묶음 (지렁이 개수) 체크 파트 
    for 탐색_y in range(N): # N 은 세로길이 이므로 y 값 
        for 탐색_x in range(M): # M 은 가로길이 이므로 x 값 
            if graph[탐색_y][탐색_x] == 1: # 첫 배추 좌표를 확인하면 
                BFS(graph, 탐색_x, 탐색_y) # BFS 실행 후 
                cnt += 1 # 카운팅 
    print(cnt) # 카운팅한 배추 묶음 개수 출력

 

처음에는 인접행렬이나 인접 리스트로 배추밭을 구현하려고 했는데, 배추밭 속에서 다수의 그래프를 찾아야 하는 문제여서 배추밭을 2차원 배열로 구현한 뒤에 순차적으로 그래프를 찾아나가고 그래프를 발견하면 BFS/DFS를 쓰면 되겠다 싶었다. 

 

근데 구현을 어떻게 할지 모르겠어서,, 구글링 해서 구현의 큰 흐름은 파악했으나, 사람들이 변수명을 너무 막 써서 이게 어떤 값인지 잘 모르겠어서.. 내가 머리 조금 써서 한글로 수정을 했다. 

 

테스트 케이스 T를 먼저 입력받고, 각각의 T에 대한 for 문으로 M(가로길이), N(세로 길이), K(배추 개수)를 입력받아 각각 0의 값을 가지는 N * M의 2차원 배열(행렬)을 만들었고, 이후 추가로 입력받는 배추 X, Y 좌표값에 대해서는 배열의 값만 1로 바꾸어줬다. 

 

그리고 이후로는 각 좌푯값을 돌면서 배추를 발견하면 (1을 만나면) 하나의 그래프를 발견했다고 보고 BFS를 실행하여 그 그래프의 값을 0으로 만든 후 그래프 개수를 카운팅 하였고, 마지막에 총 그래프 묶음을 출력해주었다. 

 

여기서 deque 를 가져다 썼는데, 이유는 list로 쓰면 pop 메서드를 쓸 때 O(N)의 복잡도를 가지지만, deque는 O(1)의 복잡도를 가져서 이다. 

 

DFS 사용

import sys
sys.setrecursionlimit(10000)

def DFS(graph, 탐색_x, 탐색_y):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    for i in range(4):
        인접_x = 탐색_x + dx[i]
        인접_y = 탐색_y + dy[i]

        if ( 0 <= 인접_x < M and 0 <= 인접_y < N and graph[인접_y][인접_x] == 1 ):
            graph[인접_y][인접_x] = 0
            DFS(graph, 인접_x, 인접_y)
    return

T = int(input())

for _ in range(T):
    cnt = 0
    M, N, K = map(int, input().split())
    graph = [ [0] * M for _ in range(N) ]

    for _ in range(K):
        배추_x, 배추_y = map(int, input().split())
        graph[배추_y][배추_x] = 1

    for 탐색_y in range(N):
        for 탐색_x in range(M):
            if graph[탐색_y][탐색_x] == 1:
                DFS(graph, 탐색_x, 탐색_y)
                cnt += 1
    print(cnt)

BFS의 차이점으로 DFS는 재귀를 사용하였다. 여기서 sys.setrecursionlimit(10000) 이 코드는 재귀의 제한을 만 번으로 제한한다는 뜻인데 기본값이 1000으로 문제를 풀기에는 턱없이 적어서 한도를 늘려주는 코드를 작성하여야 했다. 

 

큰 틀은 BFS 와 같고 재귀를 사용한다는 점만 차이가 있다. 

 

[스터디 리뷰]

graph[y][x] 로 했는데, 일반적으로는 행렬로 m * n 으로 한다는 듯. 보통은 n m 으로 인풋을 주지만 이 문제에서는 다르게 줘서 내가 헷갈린듯? 

 

그리고 또 BFS /DFS 쓸 때 보통은 탐색하면서 1->2->3... 처럼 숫자를 올려가는게 국룰이라고 한다! 다른 FS 문제도 다 풀어봐야지