[백준] 1012번 유기농 배추

Bini by Bini·2023년 2월 6일
0

코테

목록 보기
7/24

❓문제

[실버2]
https://www.acmicpc.net/problem/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)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

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

예제 입력1

2
10 8 17
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6
10 10 1
5 5

예제 출력1

5
1

예제 입력2

1
5 3 6
0 2
1 2
2 2
3 2
4 2
4 0

예제 출력2

2

💭 아이디어

이 문제는 DFS, BFS 모두로 풀 수 있다.
나는 DFS로 먼저 풀이하였다. 그러나 BFS부터 해설..

[BFS로 풀 경우]
1로 묶을 수 있는 구역마다 지렁이 1마리가 필요하므로 구역이 총 몇개인지 확인해야 한다.
따라서 그래프를 순회하다가, 1인 칸을 발견하면 bfs를 수행한다.
bfs를 수행하면 해당 지점을 0으로 변경하여 방문처리를 하고, 해당 지점의 상하좌우를 탐색하며 상하좌우 지점이 1인 경우 이또한 0으로 변경하여 방문처리를 한다.
이렇게 한 구역에 대해 bfs가 끝나면 그 구역은 모두 1에서 0으로 값이 바뀐다. 1인 칸을 발견할 때마다 bfs를 수행하고, total 값(구역 개수)를 1씩 증가시키면 총 몇개의 구역으로 나눌 수 있는지(=지렁이가 몇마리 필요한지) 알 수 있다.

[DFS로 풀 경우]
전체 그래프에 대해 dfs를 수행한다.
만약 현재 노드의 값이 1이면 상하좌우에 대해서 dfs함수를 재귀호출하며 더 깊게 탐색을 진행한다. 상하좌우 지점이 1인 경우 0으로 변경하여 방문처리를 하고, 그 지점에서 또 상하좌우로 재귀호출을 하여 깊은 탐색을 하도록 한다. 재귀가 끝나면 True를 반환하여 total값을 증가시킨다.
만약 이중포문에서 그래프를 순회할 때 현재 노드의 값이 0이면, 바로 false를 반환하며 dfs함수가 종료된다.
나머지 내용은 bfs와 같다.

❗ 풀이

1. BFS

from collections import deque

T = int(input())

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# bfs
def bfs(a, b):
    q = deque()
    q.append((a, b))
    array[a][b] = 0 # 방문처리
    
    while q:
        x, y = q.popleft()
        
        for i in range(4): # 상하좌우 이동
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or ny < 0 or nx >= M or ny >= N: # 좌표 확인
                continue
            if array[nx][ny] == 1: # 배추가 심어져 있으면
                q.append((nx, ny))
                array[nx][ny] = 0

for i in range(T): # T번 반복
    M, N, K = map(int, input().split())
    array = [[0] * N for i in range(M)]

    for j in range(K):
        x, y = map(int, input().split())
        array[x][y] = 1
    # print(array)
    
    # 그래프를 순회하며 탐색
    total = 0
    for i in range(M):
        for j in range(N):
            if array[i][j] == 1: # 배추가 심어져 있으면 bfs 수행
                bfs(i, j)
                total += 1
	print(total)

2. DFS

import sys
sys.setrecursionlimit(10**6)

T = int(input())

# dfs
def dfs(x, y):
    if x < 0 or y < 0 or x >= M or y >= N: # 재귀호출을 했을 때 좌표 확인
        return False
    if array[x][y] == 1: # 배추가 심어져 있으면
        array[x][y] = 0 # 0로로 바꾸어 방문표시
        dfs(x-1, y)
        dfs(x+1, y)
        dfs(x, y+1)
        dfs(x, y-1)
        return True
    return False # 배추가 심어져 있지 않은 경우

for i in range(T): # T번 반복
    M, N, K = map(int, input().split())
    array = [[0] * N for i in range(M)]

    for i in range(K):
        x, y = map(int, input().split())
        array[x][y] = 1
    # print(array)
    
    # 그래프를 순회하며 탐색
    total = 0
    for i in range(M):
        for j in range(N):
            if dfs(i, j) == True:
                total += 1
    print(total)

✅ Comment

  1. N 과 M, 행과 열이 헷갈린다.
    이 문제에서는 N이 열, M이 행로 생각해야 한다. 예제 입력값들을 보면 이해가 된다.
    [x][y]로 접근하려면 array = [[0] * N for i in range(M)] 이와 같이 배열을 생성해야 한다.

  2. DFS로 접근할 경우 아래의 두줄을 적지 않으면 런타임 에러(Recursion Error)가 발생한다.

import sys
sys.setrecursionlimit(10 ** 6)

python3는 재귀함수 깊이가 1000까지로 매우 얕다.
따라서 재귀로 문제를 풀 경우 이 제한에 걸릴 가능성이 있어 이를 sys 모듈의 setrecursionlimit() 함수를 통해 임의로 늘려주어야 한다. 또는 재귀를 사용하지 않는, BFS로 문제를 풀이할 수도 있다.

  1. 이코테 음료수 얼려 먹기와 매우 유사하다. (사실 입력 부분을 제외하면 같은 문제라고 보아도 무방하다.)

같은 문제에 대해 여러 방식으로 풀이가 가능하면 그 풀이를 가능한 다 해보고자 노력하자 !

profile
My Precious Records

0개의 댓글