[python]1012번 유기농 배추

 

import sys
sys.setrecursionlimit(123456) #파이선 한계 돌파
input = sys.stdin.readline
def dfs(iniy,inix):  #탐색 함수
    for i in range(4):
        dx = inix+x[i]
        dy = iniy+y[i]
        if 0<=dx<clmn and 0<=dy<row and stg[dy][dx] and not visit[dy][dx]:
            visit[dy][dx] = 1
            dfs(dy,dx)
for _ in range(int(input().strip())):
    clmn,row,cnt = map(int,input().split()) 
    stg = [[0 for i in range(clmn)]for j in range(row)]
    visit = [[0 for i in range(clmn)]for j in range(row)] #중복 진입 방지
    for i in range(cnt):
        tx,ty = map(int,input().split())
        stg[ty][tx] = 1
    x = [0,0,-1,1] #4방면으로 나아가기 위한 값 설정
    y = [1,-1,0,0] 
    rst= 0
    for i in range(row):
        for j in range(clmn):
            if stg[i][j] and not visit[i][j]:   #새로운 배추농장 확인
                visit[i][j] = 1
                rst+=1   #새로운 배추 컴포넌트 값 갱신
                dfs(i,j)   # 연결된 배추 탐색 시작
    print(rst)

컴포넌트 확인 문제였다.

사실 단지번호 붙이기 문제(2667번)와 너무 똑같아 복습 느낌으로 풀어보았다.

 

pyoong님의 풀이

import sys
sys.setrecursionlimit(11111)

def dfs(i, j):
    arr[i][j] = 0
    for k in range(4):
        ni = i + di[k]
        nj = j + dj[k]
        if 0 <= ni < n and 0 <= nj < m and arr[ni][nj] == 1:
            dfs(ni, nj)

t = int(input())

di = [-1, 1, 0, 0]
dj = [0, 0, -1, 1]

for _ in range(t):
    m, n, k = map(int, input().split())
    arr = [[0] * m for _ in range(n)]    #가장 놀라운 부분으로, visit부분과 stg리스트를 하나로 합쳤다.

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

    cnt = 0
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 1:
                cnt += 1
                dfs(i, j)
    print(cnt)

굳이 visit stg를 나눌 이유가 없었다. 하나로 합쳐서 코드를 간결하게 하였다.