[BOJ-2583] 영역구하기

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

2583번: 영역 구하기

---

[풀이]

BFS로 풀었다.

처음 문제를 접근했을 때, BFS보다 DFS를 떠올랐다.

BFS로 하게되면 인접한 부분의 카운트횟수가 같기때문이다. 

 

나중에 BFS를 이용해서 떠오른건

현위치에 대한 방문여부를 확인한뒤에

아직 방문하지 않은 상태라면 카운트를 하고 방문상태로 바꿔준다.

 

그리고 큐가 비어질때까지 카운트하는 거다.

---

[코드- python3- bfs]

import sys
from collections import deque
q=deque()
input=sys.stdin.readline
dy=(-1,1,0,0)
dx=(0,0,-1,1)

def bfs(y,x):
    global MAP,M,N, visited
    q.append((y,x))
    area=0
    while q:
        cury, curx = q.popleft()
        #현위치가 아직 방문안한 상태라면
        if not visited[cury][curx]:
            #방문횟수 +1
            area+=1
            visited[cury][curx]=True

            #현위치의 상하좌우 탐색
            for i in range(4):
                nexty=cury+dy[i]
                nextx=curx+dx[i]
                if (nexty>=0 and nexty<M) and (nextx>=0 and nextx<N):
                    if (MAP[nexty][nextx]==0) and (not visited[nexty][nextx]):
                        q.append((nexty, nextx))
    return area


if __name__=='__main__':
    M,N,K=map(int, input().strip().split())
    MAP=[[0]*N for _ in range(M)]
    
    visited=[[False]*N for _ in range(M)]
    for _ in range(K):
        #아래 꼭짓점좌표, 위꼭짓점 좌표
        dlx, dly, urx, ury= map(int, input().strip().split())
        for y in range(dly, ury):
            for x in range(dlx, urx):
                MAP[y][x]=1

    A=[]
    for y in range(M):
        for x in range(N):
            if (MAP[y][x]==0) and (not visited[y][x]):
                A.append(bfs(y,x))
            
    print(len(A))
    print(' '.join(map(str, sorted(A))))

 

[코드 - python3 - dfs]

## DFS 코드 ##
import sys
sys.setrecursionlimit(10**8)
input=sys.stdin.readline
dy=(-1,1,0,0)
dx=(0,0,-1,1)

def DFS(cury, curx):
    global MAP,M,N, visited, area

    #현위치 방문
    visited[cury][curx]=True
    area+=1
    
    #현위치의 상하좌우 탐색
    for i in range(4):
        nexty=cury+dy[i]
        nextx=curx+dx[i]
        if (nexty>=0 and nexty<M) and (nextx>=0 and nextx<N):
            if (MAP[nexty][nextx]==0) and (not visited[nexty][nextx]):
                DFS(nexty, nextx)

if __name__=='__main__':
    M,N,K=map(int, input().strip().split())
    MAP=[[0]*N for _ in range(M)]
    visited=[[False]*N for _ in range(M)]
    
    #아래 꼭짓점좌표, 위꼭짓점 좌표를 구하여
    #K개의 직사각형들은 1로 색칠한다.
    for _ in range(K):
        dlx, dly, urx, ury= map(int, input().strip().split())
        for y in range(dly, ury):
            for x in range(dlx, urx):
                MAP[y][x]=1

    A=[]
    # 색칠한 직사각형을 제외한 나머지는 0으로 구성되어있다.
    # 아직방문을 안한상태이고, MAP[y][x]=0 인 상태라면
    # DFS함수를 호출하여 (색칠안한) 연결된 곳이 몇개인지 구한다.
    for y in range(M):
        for x in range(N):
            if (MAP[y][x]==0) and (not visited[y][x]):
                area=0
                DFS(y,x)
                A.append(area)
            
    print(len(A))
    print(' '.join(map(str, sorted(A))))

---

[실패코드 1]

 

dfs를 이용해서 풀고싶으나, 런타임에러가 떴다.

테스트 케이스가

100 100

0 0 1 1

일때 9999가 나와야되는데 Memory Error: StackOverflow가 뜬다.

import sys
sys.setrecursionlimit(10**8)
input=sys.stdin.readline
dy=(-1,1,0,0)
dx=(0,0,-1,1)
area=0

def DFS(cury, curx):
    global MAP,M,N, visited, area

    #현위치 방문
    visited[cury][curx]=True
    area+=1
    
    #현위치의 상하좌우 탐색
    for i in range(4):
        nexty=cury+dy[i]
        nextx=curx+dx[i]
        if (nexty>=0 and nexty<M) and (nextx>=0 and nextx<N):
            if (MAP[nexty][nextx]==0) and (not visited[nexty][nextx]):
                DFS(nexty, nextx)


if __name__=='__main__':
    M,N,K=map(int, input().strip().split())
    MAP=[[0]*N for _ in range(M)]
    visited=[[False]*N for _ in range(M)]
    for _ in range(K):
        #아래 꼭짓점좌표, 위꼭짓점 좌표
        dlx, dly, urx, ury= map(int, input().strip().split())
        for y in range(dly, ury):
            for x in range(dlx, urx):
                MAP[y][x]=1

    A=[]
    for y in range(M):
        for x in range(N):
            if (MAP[y][x]==0) and (not visited[y][x]):
                area=0
                DFS(y,x)
                A.append(area)
            
    print(len(A))
    print(' '.join(map(str, sorted(A))))