[백준] 16932_모양만들기 - 파이썬

🔈 문제

N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다.
1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 연결 요소를 모양이라고 부르자. 모양의 크기는 모양에 포함되어 있는 1의 개수이다.
배열의 칸 하나에 들어있는 수를 변경해서 만들 수 있는 모양의 최대 크기를 구해보자.

 

📝입력

첫째 줄에 배열의 크기 N과 M이 주어진다. 둘째 줄부터 N개의 줄에는 배열에 들어있는 수가 주어진다.

 

📑출력

첫째 줄에 수 하나를 변경해서 만들 수 있는 모양의 최대 크기를 출력한다.

 

🚫제한

$ 2 <= N, M <= 1000 $
0과 1의 갯수는 하나 이상이다.

 

📚 문제 풀이

 

딱 문제를 보자마자 어떻게 풀어야 할지 감이왔다.

방문체크 배열에 현재 자기가 속한 그룹을 담아 둔뒤 그 그룹의 1의 갯수를 따로 dict에 담아 놓는다. 즉 이중반복문을 통해 그래프를 돌면서 1이라면 BFS를 돌려 그룹으로 묶어주었다.

 

그렇게 방문 배열에 각각 속한 그룸을 담아두었다면, 이제 다시 반복문을 돌아서 0인 곳을 찾는다. 만약 0이라면 상하좌우에 어떤 그룹이 있는지 체크해준다. 상하좌우에 같은 그룹이 포함되어 있는 경우도 있는데 같은 그룹은 다시는 포함 안되게 하기 위해 set 자료구조를 사용하였다.

 

그렇게 상하좌우에 있는 그룹을 파악했으면 dict에 저장해놓은 각각 1을 포함하고 있는 갯수를 불러와 더해준뒤 최대값을 출력해주었다.

 

💻 코드 1

from collections import deque
import sys
input= sys.stdin.readline
 
# 1갯수 각각 도형에 카운트
# 마지막에는 0만 찾아 다니면서 상하좌우 1의 조각 갯수 더함
 
dx = [1,0,-1,0]
dy = [0,1,0,-1]
n,m = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(n)]
visited = [[0]*(m) for _ in range(n)]
 
dic = dict()
 
# 1이의 갯수를 체크하기 위한 탐색 
def bfs(a: int,b: int,c: int,pos: int)-> int:
    queue = deque()
    queue.append([a,b,c])
    visited[a][b] = pos
    cnt_tmp = 1
    while queue:
        x,y,cnt = queue.popleft()
 
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
 
            if visited[nx][ny] == 0 and graph[nx][ny] == 1:
                cnt_tmp += 1
                queue.append([nx,ny,cnt+1])
                visited[nx][ny] = pos
    #print('last', cnt_tmp)
    # 1의 묶음 갯수
    return cnt_tmp
 
# 각각의 1뭉탱이 key값은 idx로 두었다.
idx = 1
for i in range(n):
    for j in range(m):
        # 1이고, 아직 방문안했다면
        if graph[i][j] == 1 and visited[i][j] == 0:
            tmp = bfs(i,j,1,idx) # 1의 뭉탱이 갯수
            dic[idx] = tmp # dict에 저장 
            idx += 1 
tot = []
# 다시 반복문 돌아 0을 찾는다.
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            side =set()
            # 상하좌우 1뭉탱이 키값을 side에 
            for k in range(4):
                nx = i+dx[k]
                ny = j+dy[k]
 
                if nx < 0 or ny < 0 or nx >= n or ny >= m:
                    continue
                if visited[nx][ny] != 0:
                    side.add(visited[nx][ny])
            # tot는 모든 0의 상하좌우 list
            if side not in tot:
                tot.append(side)
#print(tot)
result = []
for ans in tot:
    for_sum = 0
    ans = list(ans)
    # 키값 불러서 0을 1로 바꾸면 몇인지 확인
    for i in ans:
        for_sum += dic[i]
    #print(for_sum)
    result.append(for_sum)
 
print(max(result)+1)

위의 코드는 시간초과가 발생하였다.

이중반복문을 두번이나 돌았고, (1을 찾기 위해, 0을 찾기 위해), 연산을 너무 세분화 하여 반복문을 여러 차례 돌게하였다.

그래서 1을 찾기 위해 이중 반복문을 돌때 0의 위치도 stk라는 list에 저장해둔뒤 나중에 다시 이중반복문을 돌지 않게 최적화 하였고, 또 세분화된 것들을 한번에 처리하였다.

 

💻 코드 2

from collections import deque
import sys
input= sys.stdin.readline
 
 
dx = [1,0,-1,0]
dy = [0,1,0,-1]
n,m = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(n)]
visited = [[0]*(m) for _ in range(n)]
 
dic = dict()
# 1갯수 각각 도형에 카운트
# 마지막에는 0만 찾아 다니면서 상하좌우 1의 조각 갯수 더함
 
def bfs(a,b,c,pos):
    queue = deque()
    queue.append([a,b,c])
    visited[a][b] = pos
    cnt_tmp = 1
    while queue:
        x,y,cnt = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
 
            if visited[nx][ny] == 0 and graph[nx][ny] == 1:
                cnt_tmp += 1
                queue.append([nx,ny,cnt+1])
                visited[nx][ny] = pos
    return cnt_tmp
idx = 1
stk = []
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1 and visited[i][j] == 0:
            dic[idx] = bfs(i,j,1,idx)
            idx += 1
        # 0이면 stk에 저장
        elif graph[i][j] == 0:
            stk.append([i,j])
res = 0
for i,j in stk:
 
    four = 0 # 상하좌우 1의 갯수 합
    pre = [] # 같은 연산 두번 방지하기 
    for k in range(4):
        nx = i+dx[k]
        ny = j+dy[k]
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
            continue
        level = visited[nx][ny]
        if level!=0 and level not in pre:
            four += dic[level]
            pre.append(level)
        #print('four', four)
    if res < four+1:
        res = four+1
print(res)

 

이렇게 최적화하니 통과하였다!!ㅎ

 

🍭 시행착오

 

🔗 문제링크 모양 만들기

16932번: 모양 만들기