[백준/python] 1012번: 유기농배추

1012번: 유기농 배추 (acmicpc.net)

1012번: 유기농 배추

 

 

 

코드

import sys
input = sys.stdin.readline
dx= [0,0,1,-1]
dy= [1,-1,0,0]

t = int(input())
for _ in range(t):
    m,n,k=map(int,input().split()) #가로세로 배추개수
    qocn=[[0]*(m+2) for i in range(n+2)] #배추밭배추위치
    visitdi = {} #전체적으로이미방문했나
    ans=0
    for i in range(k):
        x,y=map(int,input().split()) #가로세로
        qocn[y+1][x+1]=1
        visitdi[(y,x)] = 0
    #모든칸에대해반복
    #~1이면 상하좌우1인지보고스택에넣기
    #그거꺼내면서 계속 탐색
    #스택다털리면 ans+1
    #~이걸 반복하는데 대신 이미 확인한곳 또가면안되잖슴
    #그건 비짓 딕셔너리만들어서확인 ㄱ
    for i in range(n): #세로
        for j in range(m): #가로
            if qocn[i+1][j+1]==1 and visitdi[(i,j)]==0:
                st=[(i,j)]
                visitdi[(i,j)]=1
                while st:
                    now=st.pop()
                    a,b=now[0],now[1]
                    for l in range(4):
                        if qocn[a+1+dx[l]][b+1+dy[l]]==1 and visitdi[(a+dx[l],b+dy[l])]==0:
                            st.append((a+dx[l],b+dy[l]))
                            visitdi[(a+dx[l],b+dy[l])]=1
                ans+=1
    print(ans)

풀이

깊이우선탐색을 이용한다.

테스트케이스 입력받은만큼 반복한다.

가로,세로,배추개수,배추위치를 모두 입력받고 qocn 이중리스트를 만들어 표시한다. 이때 나중에 탐색할 때 편하려고 둘레에 0을 넣어준다. 방문했는지를 확인하기위해 visitdi라는 딕셔너리를 만들어주고 우선 0이라고 저장해둔다.

모든 칸에대해 배추가 있다면 상하좌우에 배추가 있는지 확인하고 그 공간을 세어줘야하므로 이중for문을 돌린다.

만약 배추도 있고 아직 방문한 적도 없으면 ans+1을 해주고, 스택에 넣어주고, 방문했다고 visitdi에 1넣어준다.

스택이 텅 빌때까지 while반복한다. ~현재노드는 스택에서 pop해주고 그 노드의 상하좌우를 배추있는지 방문했는지 확인하여 방문여부표시하고, 스택에 넣어준다. 상하좌우는 dx, dy리스트 만들어서 for문 4번 반복하는 식으로 한다.

전부반복하고 print(ans)해준다.