[Python] 2583번 영역 구하기 / DFS

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

 

피드백을 바탕으로 수정한 코드 -->

#4방향 모두 탐지
dx=[-1,0,0,1]
dy=[0,-1,1,0]

def dfs(x,y):
    '''
    if board[y][x]==1:
        return
    '''
    
    cnt=1
    board[y][x]=1 #방문처리
    stack=[[x,y]]
    while stack:
        s=stack.pop()
        #board[s[1]][s[0]]=1 #방문처리
        
        for d in range(4): #굳이 8방향으로 탐색할 이유가? -> 4방향으로 해두 됌
            nx=s[0]+dx[d]
            ny=s[1]+dy[d]
            if 0<=nx<n and 0<=ny<m:
                if board[ny][nx]==0:
                    board[ny][nx]=1 #이 때 방문처리하는게 맞음
                    cnt+=1
                    stack.append([nx,ny])
                    
    list_c.append(cnt)

m,n,k=map(int,input().split()) #m=>y,n=>x
board=[[0 for _ in range(n)] for _ in range(m)]

for _ in range(k):
    lx,ly,rx,ry=map(int,input().split()) #lx=0 ly=2 rx=4 ry=4
    
    for i in range((m-1)-ly,((m-1)-ly)-(ry-ly),-1): #m=5-> (m-1)-ly=2 ~ ((m-1)-ly)-(ry-ly)=0 ,-1
        for j in range(lx,lx+(rx-lx)): #n=7-> lx=0 ~ lx+(rx-lx)=4
            board[i][j]=1

    
res=0     
list_c=[]
for y in range(m):
    for x in range(n):
        if board[y][x]==0: #수정
            dfs(x,y) ## 매개변수도 y,x로 넘기면 덜 헷갈릴 것
            res+=1
print(res)
print(' '.join(str(x) for x in sorted(list_c)))
#for i in sorted(list_c):
#    print(i,end=' ')

 

 

원래 코드에서 받았던 코드의 피드백은 아래와 같았다.

 

<피드백>

1) 재귀 함수도 아닌데 왜 함수 안에 return이? 

2) 8방향 탐색을 할 이유가..?

3) append하기 전에 방문 처리를 하는 것이 더 효율적이다 -> 안 그러면 방문했음에도 스택 안에 들어가 어쨌든 다시 확인하게 되므로

4) 마지막 출력문도 꼼수 있을 듯

 

 

물론 문제가 쉬운 것도 있지만 예전에는 감도 못 잡았을 문제를 차근차근 풀어나가게 되는 발전이 보여서 뿌듯하다.

같이 스터디해주셔서 감사할 따름이다.