[ BOJ 1012 ] 유기농 배추(Python)

문제

https://www.acmicpc.net/problem/1012

분리된 영역의 개수를 세면 되는 문제다. ez

문제 풀이

배추가 심어진 위치를 모두 주어주기 때문에 그대로 차곡차곡 그래프를 만들면 된다.

1. 입력 받은 위치 (x,y) 를 key 값으로 갖게 그래프에 추가해준다.
2. (x,y)의 상하좌우 좌표가 그래프에 key 값으로 존재하면 양방향으로 이어준다.

if (nx,ny) in graph:
   graph[(nx,ny)].append((x,y))
   graph[(x,y)].append((nx,ny))

3. 만약 방문안한 좌표이면 방문 체크를 해주고, 해당 좌표와 연결된 좌표들을 pop해서 dfs에 한번 더 넣어준다.
4. dfs 함수 내에서 방문 한 좌표이면 연결됐다는 의미이므로 return 0을 해준다. 방문 안한 좌표이면 return 1을 해준다.
5. dfs의 리턴값을 count 변수에 모두 더해준 뒤 출력한다.

코드

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    #배추밭 행 m, 배추밭 열 n, 배추 개수 k
    m,n,k = map(int,input().rsplit())
    graph = {}
    visited = [[0 for col in range(n)] for row in range(m)]
    count = 0
    ground = []
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]

    for _ in range(k):
        x,y = map(int,input().rsplit())
        ground.append((x,y))
        
        graph[(x,y)]=[]
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]

            if (nx,ny) in graph:
                graph[(nx,ny)].append((x,y))
                graph[(x,y)].append((nx,ny))

    def dfs(i,j):
        if visited[i][j]==0:
            visited[i][j]=1
            
            while graph[(i,j)]:
                temp = (graph[(i,j)].pop(0))
                dfs(temp[0],temp[1])
            return 1
        else:
            return 0

    for baechoo in ground:
        count += dfs(baechoo[0],baechoo[1])
        
    print(count)