구현 문제 풀이

🧡 백준 골드4 테트로미노

문제번호	언어	메모리	시간
14500	PyPy3	121504 KB	2376 ms

잘못 푼 코드

문제를 잘못 읽고 5개의 도형을 모두 다 배치해야 하는 건 줄 앎..
도형의 회전/대칭 이 줄도 못읽고 그냥 그대로 코딩함
로직을 다 작성한 후에야 잘못 풀었다는 것을 인지함

제발 문제좀 제대로 읽자...!!

dxy = [[0,1], [1,0], [0,-1], [-1,0]]
# i번째 도형을 x,y에 visited = aft 처리
# && aft이 1이면 near 칸 구해서 리턴하기
def setShape(x, y, i, aft):
    near = []
    for dx, dy in shapes[i]:
        visited[x+dx][y+dy] = aft
        for w, v in dxy:
            if aft and 0 <= x+dx+w < n and 0 <= y+dy+v < m and not visited[x+dx+w][y+dy+v]:
                near.append([x+dx+w, y+dy+v])
    return near

# i번째 도형이 x,y에 배치될 수 있는지 확인
def isAvailable(x, y, i):
    for dx, dy in shapes[i]:
        if 0 <= x+dx < n and 0 <= y+dy < m and not visited[x+dx][y+dy]:
            continue
        else:
            return False
    return True

def countVisit():
    res = 0
    for i in range(n):
        for j in range(m):
            res += paper[i][j]
    return res


def dfs(x, y, cnt):
    global maxResult
    global visited
    if cnt == 5:
        result = countVisit()
        maxResult = max(maxResult, result)
        return

    # 도형 순회 ; i 번째 도형
    for i in range(5):
        # 아직 사용 안한 도형이면 배치하기 & 배치 가능한 도형인지 확인
        if not used[i] and isAvailable(x, y, i):
            # visited 처리 & 인접 종이 리턴
            near = setShape(x, y, i, 1)
            # 인접 종이 dfs 순회
            for p, q in near:
                dfs(p, q, cnt+1)
            # visited 원복
            setShape(x, y, i, 0)
    
maxResult = 0
n, m = map(int, input().split())
paper = [list(map(int, input().split())) for i in range(m)]
visited = [[0] * m for i in range(n)]
used = [0] * 5

shapes = [[[0,0], [0,1], [0,2], [0,3]],
            [[0,0], [0,1], [1,0], [1,1]],
            [[0,0], [1,0], [2,0], [2,1]],
            [[0,0], [1,0], [1,1], [2,1]],
            [[0,0], [0,1], [0,2], [1,1]]]

## 내 위치, 사용한 도형 개수
dfs(0, 0, 0)
print(maxResult)

# 도형의 순서는 상관 없음
# 
# dfs에서
# 내가 위치한 곳에 가능한 도형을 다 넣어봄
# 이후 재귀로 dfs 갈 수 있는 곳으로 가봄
# visited 살펴보면서
# 이미 사용한 도형은 사용하지 못함!
# 종료조건 ㅣ 
# 도형을 다 사용했을 때 visited된 칸을 다 더해서 max면 업데이트한 후 return

다시 코드를 짰는데도 불구하고 시간초과 이슈가 계속 생겼다. 슬프다😭

pypy로 풀어서야 결국 맞춘...

sys.stdin.readline 도 사용하고 pypy도 사용했다..
python3으로 돌려보니 시간초과이슈 ㅠ

import sys
input= sys.stdin.readline
# ㅣ, ㅁ, ㄴ, ㄱㄴ 를 대칭, 회전해서 갈 수 있는 모든 경우는
# 한 지점에서 4 depth까지 가는 모든 경우의 수와 같다
def dfs(x, y, s, cnt):
    global maxResult
    if cnt == 4:
        maxResult = max(maxResult, s)
        return

    # 상하좌우 뻗어가기
    for i, j in zip(dx, dy):
        # 다음 칸이 갈 수 있는 칸인지 확인
        if 0 <= x+i < n and 0 <= y+j < m and not visited[x+i][y+j]:
            # 갈 수 있다면, dfs cnt++
            visited[x+i][y+j] = 1
            dfs(x+i, y+j, s + paper[x+i][y+j], cnt+1)
            visited[x+i][y+j] = 0

# ㅜ 대칭, 회전해서 갈 수 있는 경우를 따지고..
# 한 지점(중앙)에서 4개를 bfs한 후 일단 다 더함
# 갈 수 있는 곳 (4군데) 중 가장 작은 값을 빼서 max 업데이트
def bfs(x, y):
    global maxResult
    minest = 10e9
    christ = paper[x][y]
    wing = 0
    # 4 날개 탐색
    for i, j in zip(dx, dy):
        # 가능한가?
        if 0 <= x+i < n and 0 <= y+j < m:
            christ += paper[x+i][y+j]
            minest = min(minest, paper[x+i][y+j])
            wing += 1
    # max 값
    if wing == 3:
        maxResult = max(christ, maxResult)
    elif wing == 4:
        maxResult = max(christ-minest, maxResult)



maxResult = 0
n, m = map(int, input().split())
paper = [list(map(int, input().split())) for i in range(n)]
visited = [[0] * m for i in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for i in range(n):
    for j in range(m):
        # 내 위치, sum, depth
        visited[i][j] = 1
        dfs(i, j, 0, 0)
        visited[i][j] = 0
        bfs(i, j)

print(maxResult)

• 이 분 코드가 가장 이상적이라고 생각이 드는데, 사실 "idx가 1일 때, 왜 dfs(r, c, ....)를 전달하는지" 아직 이해 못 했다.