BOJ 백준 파이썬 16932 모양 만들기

BOJ 16946 벽 부수고 이동하기 4와 같은 문제이다.

지역탐색을 하면서 각 원소에 그룹의 번호를 매기고

그 그룹을 이루는 원소 수를 저장하는 방식

 

여기서 주의해야할 점은 그룹을 넣을 때 set() 자료구조를 사용해야한다는 점이다.

그렇지 않으면 시간초과가 난다.

아무래도 배열을 이용하면 거기서 시간이 많이 잡아 먹나보다.

set()를 쓸 때는 써야한다는 교훈을 준 문제다.

 

시간 초과 코드와 맞춘 코드 2가지를 남긴다.

 

[시간 초과 코드]

import sys
from collections import deque
from itertools import combinations
from typing import List, Literal
 
 
## 지역 탐색
def bfs(i,j):
                 q.append((i,j))
                 cnt=1
                 while q:
                        x,y=q.popleft()
 
                        for k in range(4):
                            nx=x+dx[k]
                            ny=y+dy[k]
 
                            if 0<=nx<n and 0<=ny<m:
                                if board[nx][ny]==1:
                                    if visit[nx][ny]==-1:
                                        q.append((nx,ny))
                                        visit[nx][ny]=group_num
                                        cnt+=1
                                        
                 group.append(cnt)
 
                
if __name__=='__main__':
    #sys.stdin=open("input2.txt", "rt")
    
    n,m=map(int,input().split()) ##n=행,m=열
 
    board=[list(map(int,input().split())) for _ in range(n)]
 
    q=deque()
 
    dx=[0,0,-1,1]
    dy=[1,-1,0,0]
 
    group_num=0 ##그룹 번호
    group=[]## 그룹의 원소수 저장
    visit=[[-1]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if board[i][j]==1 and visit[i][j]==-1:
                visit[i][j]=group_num
                bfs(i,j) ## 지역 탐색 시작
                group_num+=1
 
    res=0
    
    for x in range(n):
        for y in range(m):
         
           
           if board[x][y]==0:
               temp=1 ##모형을 이루는 1의 개수(1로 시작)
               check=[-1]*(len(group)) ## 그룹 지역 체크
               for k in range(4):
                   nx=x+dx[k]
                   ny=y+dy[k]
 
                   if 0<=nx<n and 0<=ny<m:
                       if board[nx][ny]==1 and check[visit[nx][ny]]==-1:
                             check[visit[nx][ny]]=1
                             temp+=group[visit[nx][ny]]
               res=max(res,temp)
 
    print(res)

import sys
from collections import deque
from itertools import combinations
from typing import List, Literal
 
 
## 지역 탐색
def bfs(i,j):
                 q.append((i,j))
                 cnt=1
                 while q:
                        x,y=q.popleft()
 
                        for k in range(4):
                            nx=x+dx[k]
                            ny=y+dy[k]
 
                            if 0<=nx<n and 0<=ny<m:
                                if board[nx][ny]==1:
                                    if visit[nx][ny]==-1:
                                        q.append((nx,ny))
                                        visit[nx][ny]=group_num
                                        cnt+=1
                                        
                 group.append(cnt)
 
                
if __name__=='__main__':
    #sys.stdin=open("input2.txt", "rt")
    
    n,m=map(int,input().split()) ##n=행,m=열
 
    board=[list(map(int,input().split())) for _ in range(n)]
 
    q=deque()
 
    dx=[0,0,-1,1]
    dy=[1,-1,0,0]
 
    group_num=0 ##그룹 번호
    group=[]## 그룹의 원소수 저장
    visit=[[-1]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if board[i][j]==1 and visit[i][j]==-1:
                visit[i][j]=group_num
                bfs(i,j) ## 지역 탐색 시작
                group_num+=1
 
    res=0
    
    for x in range(n):
        for y in range(m):
         
           
           if board[x][y]==0:
               temp=1 ##모형을 이루는 1의 개수(1로 시작)
               s=set()
               for k in range(4):
                   nx=x+dx[k]
                   ny=y+dy[k]
 
                   if 0<=nx<n and 0<=ny<m:
                       if board[nx][ny]==1:
                           s.add(visit[nx][ny])
               for t in s:
                   temp+=group[t]
               res=max(res,temp)
 
    print(res)