[BOJ 1012] 유기농 배추

Depth First Search

[BOJ 1012] 유기농 배추

문제

구조화

• 전형적인 미로 탐색 문제
• 문제를 해결하기 위해 탐색할 board 생성
• 입력된 배추의 가로, 세로 좌표에 따라 2차원 board에서 해당 좌표값을 1로 수정
• dfs로 탐색하되, 이동은 4방향으로 가능
• 시작 지점부터 4방향 탐색 후 이동 가능영역으로 이동
• 이동할 공간이 없을 경우 False return
• 이동가능하면 방문 지점 좌표를 0으로 변경 후 True return

예제 시각화

해답

dx=(1,-1,0,0) # 이동 가능 영역 x
dy=(0,0,1,-1) # 이동 가능 영역 y

def dfs(x,y):
    if x>=n or x<=-1 or y>=m or y<=-1: # 이동 불가능하면 return False
        return False
    
    if target[x][y]==1: # 이동 가능한 지점
        target[x][y]=0 # 방문 표시
        for p in range(4):
            new_x = x+dx[p] # 4방향에 대해
            new_y = y+dy[p]
            dfs(new_x, new_y) # 이동
            
        return True # 이동 후 True

    return False 
    
n=int(input())
import sys
sys.setrecursionlimit(10000) 
for i in range(n):
    cnt = 0
    m,n,k = map(int, input().split())
    target = [[0 for x in range(m)] for q in range(n)]
    for w in range(k):
        a,b= map(int,input().split())
        target[b][a] = 1
        
    for g in range(m):
        for s in range(n):
            if dfs(s,g): # 탐색 후 연결된 이동 가능한 노드 집합의 경우
                cnt+=1 # count 증가
    print(cnt)