[백준] 유기농배추 🥬

[백준] 유기농 배추🥬

---

❓문제

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

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

✅예제 출력

2

➰문제접근

이 문제는 접근하기 전에 행렬에서 방향이동에 대한 개념이 잡혀있으면 수월하게 해결할 수 있을 거 같아 전에 올렸던 '구현'이란 파트에서 정리했던 것을 참고했다.

( 0 , 0 )( 0 , 1 )( 0 , 2 )( 0 , 3 )( 0 , 4 )
 ( 1 , 0 )( 1 , 1 )( 1 , 2 )( 1 , 3 )( 1 , 4 )
 ( 2 , 0 )( 2 , 1 )( 2 , 2 )( 2 , 3 )( 2 , 4 ) 
 ( 3 , 0 )( 3 , 1 )( 3 , 2 )( 3 , 3 )( 3 , 4 )
 ( 4 , 0 )( 4 , 1 )( 4 , 2 )( 4 , 3 )( 4 , 4 )

행렬이 위처럼 구성 되어있을때 우리는 아래와 같은 형식으로 방향을 이동할 수 있다( (0,0)에서 시작했다는 가정)

     동 서 남  북
 dx = [0, 0, 1,-1]
 dy = [1,-1, 0, 0] 

 x, y = 0, 0
 for i in range(4):
     nx = x + dx[i]
     ny = y + dy[i]
     print(nx, ny) 

이런 유형의 문제를 풀 때 주어야 하는 조건으로는 이동하다 행렬안에 있는 범위를 벗어날 경우를 아래와 같이 고려해 주어야 한다.

if nx < 1 or ny < 1 or nx > n or ny > n:
         continue

그러면 이제 문제에서 주어진 조건과 결합하여 해당하는 코드를 작성해보자!

먼저 입력예제를 보면 가장 먼저오는 것은 테스트케이스 횟수이다. 그 수 만큼 반복을 돌려주면서 n, m, k 에 세로, 가로, 배추가 심어진 위치의 개수 정보들을 넣어준다.

t = int(input())

for i in range(t):
    cnt = 0
    n, m, k = map(int,input().split())
    graph = [[0]*m for _ in range(n)]

>>>
 [
     [0, 0, 0], 
     [0, 0, 0], 
     [0, 0, 0], 
     [0, 0, 0], 
     [1, 0, 0]
 ]

그리고 밑에 쭉 나오는 숫자들은 배추가 심어진 위치를 나타낸다. 그곳들을 1로 바꿔 주면 된다. 헷갈릴 수 있으므로 위 코드와 결합한 형태로 표현하는게 나을 거 같다.

t = int(input())


for i in range(t):
    cnt = 0
    n, m, k = map(int,input().split())
    graph = [[0]*m for _ in range(n)]

    for j in range(k):
        x, y = map(int,input().split())
        graph[x][y] = 1
        print(graph)

>>>
 [
     [0, 0, 1], 
     [0, 0, 1], 
     [0, 0, 1], 
     [0, 0, 1], 
     [1, 0, 1]
 ]

이제 문제에서 주어진 조건과 기존에 행렬에서의 고려할 점들을 결합해 bfs함수를 구현해 주어야 한다. 반복문을 돌면서 이동할 때 1을 만날경우 처리가 된 인덱스이므로 0으로 처리한후 큐에 담아주고, 큐를 팝하면서 큐에 아무런 값일 없을때까지 while문을 돌려주어야 한다.

from collections import deque

# 동서남북으로 이동하기 위한 수단
dx = [0,0,1,-1]
dy = [1,-1,0,0]


def bfs(graph, a, b):
    queue = deque()
    queue.append((a,b))
    graph[a][b] = 0

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx < 0 or nx >=n or ny < 0 or ny >= m:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))
    return

이제 위에 있는 코드들을 결합하여 정리해주면 아래와 같이 완성시킬 수 있다.

코드

from collections import deque

# 동서남북으로 이동하기 위한 수단
dx = [0,0,1,-1]
dy = [1,-1,0,0]


def bfs(graph, a, b):
    queue = deque()
    queue.append((a,b))
    graph[a][b] = 0

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx < 0 or nx >=n or ny < 0 or ny >= m:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))
    return
t = int(input())


for i in range(t):
    cnt = 0
    n, m, k = map(int,input().split())
    graph = [[0]*m for _ in range(n)]

    for j in range(k):
        x, y = map(int,input().split())
        graph[x][y] = 1
        print(graph)

    for a in range(n):
        for b in range(m):
            if graph[a][b] == 1:
                bfs(graph, a, b)
                cnt +=1
                print(graph)
print(cnt)