boj 1012 : 유기농 배추

문제 주소: https://www.acmicpc.net/problem/1012

난이도: silver 2

1.문제설명

• 가로 M, 세로 N 길이의 땅에, k개의 배추를 심어놨다.
• 배추를 해충으로부터 보호하기위해, 배추흰지렁이를 구입하기로한다.
• 배추 흰 지렁이는 이웃한(상,하,좌,우)배추로 이동할수 있어 붙어있는 배추는 동시에 보호받는다.
• 이때 필요한 지렁이의 개수는?

2.문제해결 아이디어.

• 특정 위치에 배추가 있다면 BFS를 통해 주변을 탐색해서 인접한 배추를 탐색하고 처리해주자.

3.문제접근법

• 모든 위치를 반복문으로 돌며, 배추가 있다면 BFS를 돌려준다.
• BFS함수 내부에서는 상하좌우 이동하여, 좌표가 그리드 안에 있고, 배추가 존재하면
  • 그 칸을 중복탐색하지 않기 위하여 0으로 표시해준다.
  • 그리고 그 칸에서 또다시 상하좌우로 움직여본다.
• 위의 과정을 통해 특정 배추로부터 붙어있는 배추를 모두 처리할 수 있고, 그 배추들은 중복되어 계산되지 않는다.

def bfs(graph,x,y):
    queue = deque()
    queue.append((x,y))
    while queue:
        x, y =queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))

    for x in range(N): #세로
        for y in range(M): #가로
            if graph[x][y] == 1:
                bfs(graph, x, y)
                graph[x][y] = 0
                cnt += 1

4.특별히 참고할 사항

• 좌표 매칭을 잘 시켜줘야한다.
• 2차원 리스트 상에서 가로, 세로 좌표 매칭시켜주는게 처음엔 익숙하지 않을수 있다.

for _ in range(T):
    cnt = 0
    M, N, K = map(int, input().split())
    # M 가로 ,N = 세로
    graph = [[0] * M for _ in range(N)]
    for i in range(K):
        x, y = map(int, input().split())
        #배추의 위치 X, Y가 주어진다. 이때 좌표평면과같이 X는 가로, Y는 세로다
        #2차원 리스트에 배치하기 위해선 graph[y축][x축] 이렇게 넣어줘야한다.
        graph[y][x] = 1

5.코드구현

import sys
from collections import deque
input = sys.stdin.readline
# 상 하 좌 우
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
#graph[x][y] -> x는 위 아래 움직임, y는 좌 우 움직임
def bfs(graph,x,y):
    queue = deque()
    queue.append((x,y))
    while queue:
        x, y =queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))

T = int(input())
for _ in range(T):
    cnt = 0
    M, N, K = map(int, input().split())
    # M 가로 ,N = 세로
    graph = [[0] * M for _ in range(N)]
    for i in range(K):
        x, y = map(int, input().split())
        graph[y][x] = 1

    for x in range(N): #세로
        for y in range(M): #가로
            if graph[x][y] == 1:
                bfs(graph, x, y)
                graph[x][y] = 0
                cnt += 1
    print(cnt)