글 읽기 - 빙산문제 왜 틀리는지 모르겠네요ㅠㅠ

hjy5405 5년 전 0

질문게시판에 있는 반례들도 다 되는것같고

여러 가지 값들로 설정도 해보면서 돌려봤는데 다 맞는 것 같아요

근데 문제 넣어보면 6%에서 바로 틀렸다고 나오네요.ㅠㅠ

혹시 어디가 잘못된 부분인지 찾아주실수있으시면 감사하겠습니다!

n,m = map(int,input().split())
tot = []
for i in range(n): # tot -> 빙산데이터 입력받는 2차원 리스트
    tot.append(list(map(int,input().split())))
vic = [] # vic -> bfs를 위해 빙산데이터 중 0이 아닌 값의 위치를 받는 리스트
for i in range(n):
    for j in range(m):
        if tot[i][j] != 0:
            vic.append([i, j])
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
sw = 0
cnt = 0
q = 0
while True:
    vic2 = []
    q += 1
    for a in vic: # 년도 1년 증가시 빙산의 값이 1만큼 감소하고 0이 된 빙산은 vic리스트에서 제거
        tot[a[0]][a[1]] -= 1
        if tot[a[0]][a[1]] > 0:
            vic2.append(a)
    tot_c = []
    for i in range(n): # tot_c -> 빙산이 이어져있는지를 bfs로 판단하기 위해 메모리제이션을 위한 2차원 리스트 0이면 원래 0인위치, 처음위치와 이어져있으면 -1, 떨어진 부분은 1
        tot_c.append([0]*m)
    vic = vic2[:]
    for a in vic:
        tot_c[a[0]][a[1]] = 1 
    if vic == []: # 빙산이 모두 녹으면 0출력
        cnt = 0
        break
    b = [vic[0]]
    while True: #빙산이 이어져있는지 bfs로 검사하는 부분
        for a in b:
            tot_c[a[0]][a[1]] = -1
        b2 = []
        for a in b:
            for i in range(4):
                if tot_c[a[0]+dx[i]][a[1]+dy[i]] == 1 and tot[a[0]+dx[i]][a[1]+dy[i]] > 0:
                    b2.append([a[0]+dx[i],a[1]+dy[i]])
                    tot_c[a[0]+dx[i]][a[1]+dy[i]] = -1
        if b2 == []:
            break
        b = b2[:]
    for a in vic: #vic안에 tot_c값이 -1이 아니라 1인부분이 존재하면 녹지 않은 것으로 해석
        if tot_c[a[0]][a[1]] == 1:
            sw = 1
            break
    if sw == 1:
        cnt = q
        break
print(cnt)

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

문제

문제

출처

ICPC

빙산문제 왜 틀리는지 모르겠네요ㅠㅠ

hjy5405 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말