14500 - 테트로미노*
2022. 5. 3. 13:55ㆍ2022/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 |