[백준 1012번] 유기농 배추

# 테스트케이스 수
t = int(input())

count_list = []

def dfs(x,y):

    if x < 0 or x >= n or y < 0 or y >= m:
        return False
    
    if area[x][y] == 1 and not visited[x][y]:
        visited[x][y] = True
        
        nx = [-1,1,0,0]
        ny = [0,0,-1,1]
        
        for i in range(4):
            temp_x = x + nx[i]
            temp_y = y + ny[i]

            dfs(temp_x,temp_y)

        return True

    return False

for _ in range(t):
    # 세로(n), 가로(m), 배추 개수(k)
    m, n, k = map(int,input().split())

    area = [[0]*m for _ in range(n)]
    visited = [[False]*m for _ in range(n)]
    count = 0

    for _ in range(k):
        y, x = map(int,input().split())
        area[x][y]=1

    for i in range(n):
        for j in range(m):
            if dfs(i,j):
                count+=1

    count_list.append(count)


for i in count_list:
    print(i)

이번 문제는 푸는 데는 시간이 오래 걸리지 않았지만, 많은 점들을 배우고 코드를 개선할 수 있었던 아주 인상깊은 문제였다.

 

먼저 이 문제의 핵심은 dfs나 bfs 알고리즘을 사용하여 인접하게 연결되어있는 영역의 개수를 찾는 것이다 !

영역(땅)을 나타내는 2차원 배열(area)와 방문 여부를 체크하는 2차원 배열(visited)를 선언한 뒤, dfs 함수를 사용해서 정답을 구했는데, 이번에 다른 사람들의 풀이를 보면서 지저분했던 이전의 코드를 개선할 수 있었다.

 

위 dfs 함수를 보면 이전에는 False를 반환하는 경우(배열의 범위를 벗어났을 때, 갈 수 없는 영역일 때, 방문한 적 있는 영역일 때)를 중복되고, 지저분하게 코드를 작성했었는데 코드가 많이 깔끔해졌음을 알 수 있다 :)