[1012번]유기농배추 - 파이썬

T = int(input())

for twice in range(T):
    M,N,K = map(int,input().split(' '))
    field = [[0] * M for _ in range(N)]
    answer = [] 
    dx = [0,0,1,-1] #동서남북 인접한 곳의 좌표를 구하기 위함 
    dy = [1,-1,0,0]
    cnt = 0 

    #필드 초기화 
    for _ in range(K):
        x,y = map(int,input().split(' '))
        field[y][x] = 1

    #dfs정의하기 
    def dfs(x,y):
        field[x][y] = '#'

        for k in range(4): #동서남북 인접한 네 방향에 대해서 
            nx = x + dx[k]
            ny = y + dy[k]
            if 0<=nx<N and 0<=ny<M and field[nx][ny] ==1: #인접한 곳의 좌표가 범위 내이고, ==1이라면 
                field[nx][ny] = '#' #방문한 곳으로 처리해준다 
                dfs(nx,ny) #조건을 만족하는 지점에서 다시 탐색을 시작한다 
        return 

    for i in range(N):
        for j in range(M):
            if field[i][j] == 1:
                cnt += 1
                dfs(i,j)

    #탐색한 횟수가 지렁이가 필요한 갯수이다. 
    print(cnt)

어제는 dfs,bfs만 풀다보니 뭔가 이 문제유형에 대한 감이 약간 잡힌 것 같았다. 그래서 그 다음 문제도 봤는데, 뭔가 풀릴 것 같은 느낌이 딱 와서 오늘 바로 풀었다. 이전 문제 유형들과 비슷해서 크게 어렵지 않게 풀었던 것 같다. 

 

지렁이 한마리가 있으면, 붙어있는 배추들은 다 깨끗해진다. 그러니까, 붙어있는 배추들의 묶음만큼 지렁이의 갯수가 필요한 것이다. 이것을 알고리즘 관점에서 보자면, dfs를 탐색한 횟수만큼이 곧 지렁이가 필요한 갯수인 것이다. 

 

이전 문제에서 사용했던 풀이를 그대로 가져와서, 활용했다.