[파이썬] 백준 14391 : 종이 조각 (골드3)

[파이썬] 백준 14391 : 종이 조각 (골드3)

14391번: 종이 조각

---

문제

---

풀이

0. 방향성 생각

• 완전탐색
• 같은 크기의 마스크를 생성하고 0 또는 1로 채운다.
• 0이면 오른쪽으로 이어붙이기.
• 1이면 아래로 이어붙이기.
• BFS를 사용해서 현재 마스크 값이 0이면 끝까지탐색 or 마스크가 1 나오기 전까지 우측으로 탐색
• 현재 마스크값이 1이면 끝까지 탐색 or 마스크가 0 나오기 전까지 아래쪽으로 탐색

1. 입력

from itertools import product as PI
from collections import deque
import sys
input = lambda: sys.stdin.readline().strip()

h,w = map(int,input().split())
arr = ''
for _ in range(h):
    arr += input()
masks = list(PI([0,1],repeat=h*w))

• 2차원으로 하는게 편한데 자꾸 오류나서 그냥 1차원으로 바꿨음

2. 함수 정의

def bfs(x,num):
    
    s = arr[x]
    q = deque([x])
    visit[x] = True
    
    while q:
        x = q.popleft()
        nx = x+1 if not num else x+w
        if not num:
            nx = x+1
            if nx%w and not visit[nx] and mask[nx] == num:
                s += arr[nx]
                visit[nx] = True
                q.append(nx)
        else:
            nx = x+w
            if 0<=nx<w*h and not visit[nx] and mask[nx] == num:
                s += arr[nx]
                visit[nx] = True
                q.append(nx)
    return int(s)

• 현재 마스크가 0인 경우에는 우측으로 탐색해야하니 다음 탐색은 x+1
• 현재 마스크가 0인 경우에는 아래쪽으로 탐색해야하니 다음 탐색은 x+w

3. 출력

answer = 0
for mask in masks:
    visit = [False]*w*h
    score = 0
    for i in range(h*w):
        if not visit[i]:
            score += bfs(i,mask[i])
    answer = max(answer,score)
print(answer)

• 각 케이스에 대해서 visit 을 False로 초기화시키고 score를 계산해서 answer를 업데이트한다.

 

---

전체코드

from itertools import product as PI
from collections import deque
import sys
input = lambda: sys.stdin.readline().strip()

h,w = map(int,input().split())
arr = ''
for _ in range(h):
    arr += input()
masks = list(PI([0,1],repeat=h*w))

def bfs(x,num):
    
    s = arr[x]
    q = deque([x])
    visit[x] = True
    
    while q:
        x = q.popleft()
        nx = x+1 if not num else x+w
        if not num:
            nx = x+1
            if nx%w and not visit[nx] and mask[nx] == num:
                s += arr[nx]
                visit[nx] = True
                q.append(nx)
        else:
            nx = x+w
            if 0<=nx<w*h and not visit[nx] and mask[nx] == num:
                s += arr[nx]
                visit[nx] = True
                q.append(nx)
    return int(s)

answer = 0
for mask in masks:
    visit = [False]*w*h
    score = 0
    for i in range(h*w):
        if not visit[i]:
            score += bfs(i,mask[i])
    answer = max(answer,score)
print(answer)

 

코멘트

쉽구만