글 읽기 - 파이썬 1퍼 반례를 알고 싶어요

ish990730 2년 전 0

하드코딩은 아니고 몸집을 점점 키워나가면서 주위 숫자 탐색해 최대값을 찾게 만들고 있는데 질문에 있는 반례는 다 넣어봤는데 아직도 안되는 반례를 찾지 못했습니다.. 어디가 문제일까요?

import collections
import sys

def find_max(board, N, M):
    res = collections.deque()
    max = 0
    for i in range(N):
        for j in range(M):
            if max < board[i][j]:
                max = board[i][j]
    for i in range(N):
        for j in range(M):
            if board[i][j] == max:
                res.append((i, j))
    return res

def find_around_index(board, visited, N, M, cur_idx):
    res = []
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    ddx, ddy = [0, 0, -1, 1], [-1, 1, 0, 0]
    for x, y in cur_idx:
        for i in range(4):#4directions
            if N > M:
                nx = x + dx[i]
                ny = y + dy[i]
            else:
                nx = x + ddx[i]
                ny = y + ddy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if visited[nx][ny] == 0:
                    res.append((nx, ny))
                    visited[nx][ny] = 1
    for i in range(N):
        for j in range(M):
            if visited[i][j] == 1:
                visited[i][j] = 0
    return res


def greedy_search(board, N, M, max_list):
    result = []
    for x, y in max_list:
        visited = [[0] * M for _ in range(N)]
        cur_idx = [(x, y)]
        visited[x][y] = 2
        res = 0
        for _ in range(4):
            max = 0
            around_idx = find_around_index(board, visited, N, M, cur_idx)
            for a, b in around_idx:
                if max < board[a][b]:
                    max = board[a][b]
            for a, b in around_idx:
                if max == board[a][b]:
                    cur_idx.append((a, b))
                    visited[a][b] = 2
                    break
        for i in range(4):
            res += board[cur_idx[i][0]][cur_idx[i][1]]
        result.append(res)
    max = 0
    for i in result:
        if max < i:
            max = i
    return max
    



N, M = map(int, sys.stdin.readline().split())
max = 0
board = [list(map(int, input().split())) for _ in range(N)]
max_list = find_max(board, N, M)
print(greedy_search(board, N, M, max_list))

kdh6429 2년 전 0

5 5

5 5 5 5 5

1 1 1 1 1

1 9 1 1 1

정답

출력

ish990730 2년 전 0

압도적 감사....

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

문제

문제

출처

ICPC

파이썬 1퍼 반례를 알고 싶어요

ish990730 2년 전 0

kdh6429 2년 전 0

ish990730 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말