글 읽기 - 로직 점검과 반례 확인 부탁드립니다.

elrion21 4년 전 0

붙잡고 계속 수정, 질문검색해봤는데 도저히 반례를 못찾겠네요.

일단 예제 테스트케이스는 통과했습니다.

###BFS
def BFS(xy):
    queue = [xy]
    while len(queue) != 0:
        bx, by = queue.pop(0)
        for i in range(4):
            ax = bx + cx[i]
            ay = by + cy[i]
            if ax>=0 and ax<M and ay>=0 and ay<N:
                if iceberg[ay][ax] >0 and visited2[ay][ax] == 0:
                    visited2[ay][ax] = 1
                    queue.append([ax,ay])

###큐 선언
queue = []

###이동방향 선언
cx = [0,0,-1,1]
cy = [-1,1,0,0]


###입력
N, M = list(map(int,input().split()))
###빙산 리스트 선언
iceberg = []

###빙산이 있었던 곳 나타내기 위한 리스트 선언
visited = [[0]*M for _ in range(N)]
###최초의 시간(년)을 저장할 변수 선언
year = 0

###빙산의 가능한 최대 높이 선언
maxHeight = 0
for i in range(N):
    a = list(map(int,input().split()))
    aHeight = max(a)
    if aHeight > maxHeight:
        maxHeight = aHeight
    iceberg.append(a)

###빙산의 최대 높이가 0이 될 때 까지 반복
while maxHeight != 0:
    #BFS방문 체크를 위한 리스트 선언
    visited2 =[[0]*M for _ in range(N)]

    #빙산이 있었던 곳 나타내기 위한 리스트 선언
    visited = [[0]*M for _ in range(N)]
    #빙산의 갯수를 저장할 변수 선언
    count = 0
    for y in range(N):
        for x in range(M):
            if iceberg[y][x] >0: #iceberg[y][x]에 빙산이 존재한다면(높이가 0이상이라면)
                seaWater = 0 #빙산에 인접한 바다 칸 저장 변수 선언
                for i in range(4):
                    ax = x + cx[i]
                    ay = y + cy[i]
                    if ax>=0 and ax<M and ay>=0 and ay<N:
                        #인접한 바다 칸 수 만큼 저장
                        if iceberg[ay][ax] <= 0 and visited[ay][ax] != 1:
                            seaWater +=1

                if iceberg[y][x]-seaWater <0:
                    iceberg[y][x] = 0
                    visited[y][x] = 1
                else:
                    iceberg[y][x] = iceberg[y][x] - seaWater
                    if iceberg[y][x] == 0: # 빙산이 완전히 다 녹았다면 visited에 기록해주기
                        visited[y][x] = 1
    maxHeight -=1
    ###완탐 시작
    for y in range(N):
        for x in range(M):
            if iceberg[y][x] != 0 and visited2[y][x] == 0:
                count += 1
                visited2[y][x] = 1
                BFS([x,y])
    year += 1
    if count >=2:
        break

if count <2:
    print(0)
else:
    print(year)

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

문제

문제

출처

ICPC

로직 점검과 반례 확인 부탁드립니다.

elrion21 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말