글 읽기 - 틀린 원인을 모르겠습니다..

rlawhdals94 4년 전 0

고민하다가 풀이 보고 dfs랑 ㅗ,ㅏ,ㅓ,ㅜ 모양 체크해서 최댓값 구해주는 방식으로 풀었는데

케이스 다 통과하는데 틀린 이유를 모르겠습니다..

반례로

4 4

0 0 0 0

0 0 1 2

0 0 3 4

가 13이 나오던데 아무리 코드를 살펴봐도 왜 저렇게 나오는지 모르겟습니다..

원인이 뭔지 알려주실분 ㅠㅠ

"""
삼성 기출 - 테트리미노
"""
import sys


def dfs(i, j, cnt, cur_sum, visited):
    global board, N, M, max_sum

    if cnt == 4:
        max_sum = max(max_sum, cur_sum)
        return

    for (next_i, next_j) in [(i, j-1), (i, j+1), (i-1, j), (i+1, j)]:
        if (0 <= next_i < N) and (0 <= next_j < M) and visited[next_i][next_j] == 0:
            visited[i][j] = 1
            dfs(next_i, next_j, cnt + 1, cur_sum + board[i][j], visited)
            visited[i][j] = 0


def check(i, j):
    global board, N, M, max_sum

    # ㅗ
    if 1 <= i < N and 1 <= j < M-1:
        max_sum = max(max_sum, (board[i][j - 1] + board[i][j] + board[i][j + 1] + board[i - 1][j]))
    # ㅜ
    if 0 <= i < N-1 and 1 <= j < M-1:
        max_sum = max(max_sum, (board[i][j - 1] + board[i][j] + board[i][j + 1] + board[i + 1][j]))
    # ㅏ
    if 1 <= i < N-1 and 0 <= j < M-1:
        max_sum = max(max_sum, (board[i - 1][j] + board[i][j] + board[i + 1][j] + board[i][j + 1]))
    # ㅓ
    if 1 <= i < N-1 and 1 <= j < M:
        max_sum = max(max_sum, (board[i - 1][j] + board[i][j] + board[i + 1][j] + board[i][j - 1]))


N, M = map(int, sys.stdin.readline().rstrip().split())
board = list()
visited = [[0] * M] * N
for _ in range(N):
    board.append(list(map(int, sys.stdin.readline().rstrip().split())))

max_sum = 0
for i in range(N):
    for j in range(M):
        dfs(i, j, 0, 0, visited)
        check(i, j)

print(max_sum)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

틀린 원인을 모르겠습니다..

rlawhdals94 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말