글 읽기 - 게시판 반례는 모두 통과 됩니다만.. 왜 틀렸을까요 ㅜㅜ

gift2barry 1년 전 0

수영장을 3차원으로 생각해서, 매 높이미다 물이 채워질 공간을 확인하는 식으로 접근했습니다.

일단 질문 게시글의 모든 반례는 통과 합니다만.. 25%에서 틀려버리네욥..

부디 부족한 저에게 가르침을 주시면 감사하겠습니다..ㅠ

from collections import deque
import sys
sys.stdin = open('input.txt')

dr = (-1, 0, 1, 0)
dc = (0, 1, 0, -1)

def seperate(nums):    # 인풋 값 받아오기 위한 함수
    temp = [*nums]
    return map(int, temp)

def bfs(h, r, c, visited):
    test_visited, cnt = [], 1
    test_visited.append((r, c))
    Q = deque()
    Q.append((r, c))
    while Q:
        r, c = Q.popleft()

        for k in range(4):
            nr, nc = r + dr[k], c + dc[k]

            if 0 <= nr < N and 0 <= nc < M and (nr, nc) not in test_visited:

                if nr == 0 or nr == N-1 or nc == 0 or nc == M-1:
                    if field[nr][nc] < h:
                        # 만약 테두리에 물이 새면 무조건 물 다 빠지니 bfs자체를 종료
                        return 0

                # 벽이 아니면 bfs 진행
                if field[nr][nc] < h:
                    test_visited.append((nr, nc))
                    Q.append((nr, nc))
                    cnt += 1
                    continue
    
    # 임시로 방문했던 위치들 visited에 기록
    for coordinates in test_visited:
        x, y = coordinates
        visited[x][y] = 1

    return cnt      # 끝까지 bfs 돌면, 물이 차있는 공간 개수 반환


N, M = map(int, input().split())
field = [tuple(seperate(input())) for _ in range(N)]

highest = max(max(field))
ans = 0

coordinates = []    # 시간복잡도를 줄이기 위해, 방문할 위치&높이 리스트에 저장
for h in range(highest, 0, -1):
    for i in range(1, N-1):
        for j in range(1, M-1):
            coordinates.append((h, i, j))

visited = [[0] * M for _ in range(N)]
temp = highest
for c in coordinates:
    h, r, c = c

    if temp != h:    # 확인하는 높이가 바뀔때 마다 visited 초기화
        visited = [[0] * M for _ in range(N)]

    temp = h
    if field[r][c] < h and not visited[r][c]:
        ans += bfs(h, r, c, visited)
print(ans)

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

문제

문제

출처

ICPC

게시판 반례는 모두 통과 됩니다만.. 왜 틀렸을까요 ㅜㅜ

gift2barry 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말