백준[1012] - 유기농 배추

 

 

문제

1012번: 유기농 배추

 

 

 

작성한 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

T = int(input())

count = 0
result = list()

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

def dfs(x, y):
    global count

    if x < 0 or x >= M or y < 0 or y >= N:
        return False

    if graph[y][x] == 1:
        count += 1
        graph[y][x] = 0

        for i in range(4):
            dfs(x+dx[i], y+dy[i])
        
        return True

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

    for _ in range(K):
        X, Y = map(int, input().split())
        graph[Y][X] = 1

    for i in range(M):
        for j in range(N):
            if dfs(i, j) == True:
                result.append(count)
                count = 0

    print(len(result))

- 문제 유형은 이전 문제와 거의 비슷하여 DFS로 문제를 풀이하였다. (BFS로도 풀이할 수 있다고 해서 따로 연습해볼 예정이다.)

 

- 이전 문제에서 추가된 로직

   : NxN 정사각형에서 NxM 직사각형으로 변경되면서, 1열에 0이 M개만큼 존재하는 리스트가 N개 있다는 점에서 신경써야 했다.

   : K를 입력받아 해당 숫자만큼 전체 로직을 반복하면서 출력해야 했기 때문에, for문을 사용하여 K번 만큼 반복해주었다.

   : K번 만큼 반복하기 때문에 result 리스트를 for문을 돌 때마다 비워줘야 했기 때문에, result.clear()를 해주었다.

 

- 이외의 로직은 이전 문제와 거의 비슷하다고 생각되었다. (이전 글 보기)

백준[2667] - 단지번호붙이기