14500 - 테트로미노*

2022. 5. 3. 13:552022/BaekJoon_삼성 SW 역량 테스트 기출

N, M = map(int, input().split())
board = []
for _ in range(N):
    board.append(list(map(int, input().split())))
    
visit = [([False] * M) for _ in range(N)]
maxValue = 0
# 상 우 하 좌 (시계방향)
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def dfs(i, j, dsum, cnt):
    global maxValue, dx, dy
    if cnt == 4:
        maxValue = max(maxValue, dsum)
        return 
    
    # 상, 우, 하, 좌 방향
    for k in range(4):
        ndx = i + dx[k]
        ndy = j + dy[k]
        if (0 <= ndx < N) and (0 <= ndy < M) and (visit[ndx][ndy] == False):
            visit[ndx][ndy] = True
            # dsum값을 바꾸고 나서 dfs로 가면 원래 dsum 값이 변경됨
            # dsum 값을 보전하기 위해서는 dfs 들어갈때 더할 것
            dfs(ndx, ndy, dsum+board[ndx][ndy], cnt+1)
            visit[ndx][ndy] = False
            
def exec(r, c):
    global maxValue
    #상, 우, 하, 좌 방향 
    for i in range(4):
        dsum = board[r][c]
        #(상, 우, 하), (우, 하, 좌), (하, 좌, 상), (좌, 상, 우)
        for j in range(i, i+3):
            j = int(j%4)
            xi = r+dx[j]
            yj = c+dy[j]
            
            if (0<=xi<N and 0<=yj<M):
                dsum += board[xi][yj]
            # 어느 하나라도 board의 범위를 벗어나면 break
            else:
                dsum = 0
                break

        maxValue = max(maxValue, dsum)
    
        
    
for i in range(N):
    for j in range(M):
        visit[i][j] = True
        dfs(i, j, board[i][j], 1)
        visit[i][j] = False
        exec(i, j)
        
print(maxValue)

'2022 > BaekJoon_삼성 SW 역량 테스트 기출' 카테고리의 다른 글

14502 - 연구소*  (0) 2022.05.03
14501 - 퇴사*  (0) 2022.05.03
13458 - 시험감독  (0) 2022.05.03
3190 - 뱀  (0) 2022.05.03
13460 - 구슬탈출2*  (0) 2022.05.03