[백준 16932번] 모양만들기(파이썬)

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

16932번: 모양 만들기

이 문제는 처음 문제를 쓱 읽으면

'뭐야. 문제 개쉬운데?'

라는 착각을 줍니다.

물론 예제를 푸는 정도 수준은

어렵지 않는 코드이지만

그렇게하면 시간초과가 뜰 것입니다.

#백준 16932번 모양만들기
from collections import deque

N,M=map(int,input().split())

room=[]
zero=[]
ones=[]

for x in range(N):
    data=list(map(int,input().split()))
    room.append(data)
    for y in range(M):
        if data[y]==0:
            zero.append([x,y])
        if data[y]==1:
            ones.append([x,y])
dx=[0,0,1,-1]
dy=[1,-1,0,0]


def bfs():
    visited=[[False]*M for _ in range(N)]
    answer=0
    for x,y in ones:
        if visited[x][y]:
            continue
        q=deque()
        q.append([x,y])
        cnt=1
        visited[x][y]=True
        while q:
            px,py=q.popleft()
            for d in range(4):
                nx=px+dx[d]
                ny=py+dy[d]

                if nx<0 or nx>=N or ny<0 or ny>=M:
                    continue
                if visited[nx][ny]:
                    continue
                if room[nx][ny]==0:
                    continue

                q.append([nx,ny])
                visited[nx][ny]=True
                cnt+=1

        answer=max(answer,cnt)

    return answer

answer=0
for x,y in zero:
    room[x][y]=1
    tmp=bfs()
    answer=max(answer,tmp)
    room[x][y]=0

print(answer)

 

제가 처음 제출한 코드입니다.

풀이는 이렇습니다.

 

1. 0이 1로 바뀔 때 최대가 될 테니깐

0이 바뀌는 것만 구하기 위해

0의 위치를 전부 받는다

 

2. 0의 위치를 1로 바꾸로 bfs

그 중 최대를 tmp에 받는다

 

3. tmp를 answer와 비교하여, 가장 큰 걸 answer로 받는다

 

4. 1로 바꾼 좌표는 다시 0으로 돌려주고

다음껄 진행한다.

 

이 방식은 겉보기에는 논리적으로 보입니다.

일반적으로 이렇게 생각하는 게 타당해보이죠.

하지만 이 방식은 시간초과를 너무나 많이 잡아먹습니다.

 

극단적으로 만약에

 

1000 x 1000이라고 가정해봅니다.

그 중에서 0의 갯수가 900개.

그럼 900개의 0을 저렇게 바꿔주면서

bfs를 계속 진행해야합니다.

이렇게 크기가 커지면

시간이 답도 없게 커져버리니

시간초과가 떠버릴 수 밖에.

그렇다면 어떻게 해야할까...

고민끝에 구글링을 하다가

아이디어를 얻었습니다.

 

방법은 위의 visited에

그룹에 맞는 숫자를 넣어주는 겁니다.

기존에는 True False로

방문했는지 여부만 체크했다면

이번에는 이게 몇 번째 그룹의 덩어리인지 표시해주는 방식이죠.

그러면 나중에 0의 좌표를 비교할때

상하좌우만 비교하게 되고,

'어떤 그룹에 인접하는지'만 판단하여

그 인접그룹을 더하면 됩니다.

직접 코드를 보겠습니다.

 

#백준 16932번 모양만들기
from collections import deque

N,M=map(int,input().split())

room=[]
zero=[]
ones=[]

for x in range(N):
    data=list(map(int,input().split()))
    room.append(data)
    for y in range(M):
        if data[y]==0:
            zero.append([x,y])
        if data[y]==1:
            ones.append([x,y])
dx=[0,0,1,-1]
dy=[1,-1,0,0]
result=0


def bfs(x,y):
    q=deque()
    q.append([x,y])
    cnt=1
    visited[x][y]=num
    while q:
        px,py=q.popleft()
        for d in range(4):
            nx=px+dx[d]
            ny=py+dy[d]

            if nx<0 or nx>=N or ny<0 or ny>=M:
                continue
            if not visited[nx][ny]==0:
                continue
            if room[nx][ny]==0:
                continue

            q.append([nx,ny])
            visited[nx][ny]=num
            cnt+=1




    return cnt

answer=0

#1. 그룹화를 진행
group=dict()
num=1
visited=[[0]*M for _ in range(N)]
for x,y in ones:
    if visited[x][y]:
        continue

    cnt=bfs(x,y)
    group[num]=cnt
    num+=1

#2 0를 BFS
for x,y in zero:
    s=set()

    for d in range(4):
        nx=x+dx[d]
        ny=y+dy[d]

        if nx<0 or nx>=N or ny<0 or ny>=M:
            continue

        if room[nx][ny]==0:
            continue

        if visited[nx][ny] in s:
            continue
        s.add(visited[nx][ny])

    res=1

    for ss in s:
        res+=group[ss]
    result=max(result,res)

print(result)

 

저는 group을 dict으로 두어

각 그룹의 크기를 저장했고

s라는 집합을 두어

중복을 안담도록 했습니다.

https://reliablecho-programming.tistory.com/123

[알고리즘] 백준16932 모양만들기 - 파이썬

제가 참고한 코드.

공부에 도움이 되시길 바랍니다.