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

Problem

상하좌우로 붙어있는 1의 개수를 찾는문제(배추??ㅋ)

Solution

DFS로 풀기

코드설명

1)DFS로 visited배열과 원본 배열이용해 1인값 찾기
2)재귀호출

여기서 그냥 답을 내면 틀림.
sys.setrecursionlimit(10 곱하기 6) 이게 있어야됨..
디폴트는 104인데...
이걸 어떻게 판단하지.. 틀려보고 알아야하나.

Python Code

import sys
sys.setrecursionlimit(10**6)
T=int(sys.stdin.readline())
dy=[0,-1,0,1]
dx=[-1,0,1,0]

def dfs(y,x):
    visited[y][x]=True

    for i in range(4):
        tmpy=y+dy[i]
        tmpx=x+dx[i]

        if tmpy<0 or tmpx<0 or tmpy>h-1 or tmpx>w-1:
            continue
        if not visited[tmpy][tmpx] and arrList[tmpy][tmpx]==1:
            visited[tmpy][tmpx]=True
            dfs(tmpy,tmpx)
for _ in range(T):
    w,h,k=map(int,sys.stdin.readline().split())

    visited=[[False]*w for _ in range(h)]
    arrList=[[0]*w for _ in range(h)]
    re = []
    for _ in range(k):
        a,b=map(int,sys.stdin.readline().split())
        arrList[b][a]=1


    for i in range(0,len(arrList)):
        for j in range(0,len(arrList[i])):
            if not visited[i][j] and arrList[i][j]==1:
                re.append(1)
                dfs(i,j)
    print(len(re))