글 읽기 - 25%에서 틀렸습니다 나오는데 반례 부탁드려도 될까요?

kjkj5868 2년 전 0

일단 문제 테케랑 다른 질문글들에서 제가 찾아본 반례들에는 깔쌈하게 잘 들어맞는데 어디서 잘못했을까요..?

#1012 유기농 배추
T= int(input())
for case in range(1,T+1):
    m,n,k=map(int,input().split()) #가로길이,세로길이, 배추가 심어진 위치의 개수
    field=[[0 for _ in range(m)]for _ in range(n)]
    for i in range(k):
        x,y=map(int,input().split())
        field[y][x]=1
    
    r=[0 for _ in range((m+1)*(n+1))] # 테이블 ; 1x1일 때 배열 크기 문제 회피를 위해 
    Area=[0 for _ in range((m+1)*(n+1))] # 보정을 위해
    num=0 # 초기화
    for y in range(n):
        for x in range(m):
            if field[y][x]>0: # 배추를 만나면
                if x-1<0: # 범위 넘어가서 - 가버리면
                    left=0 # 가버리는거 방지
                else:
                    left=field[y][x-1] # 배추 왼쪽 픽셀
                if y-1<0: # 범위 넘어가서 - 가버리면
                    abv=0 # 메챠쿠챠 가버리는거 방지
                else:
                    abv=field[y-1][x] # 배추 위쪽 픽셀
                
                if left==0 and abv==0: # 모두 0이라면
                    num+=1
                    r[num]=num 
                    field[y][x]=num 
                    Area[num]=1 # 업데이트

                elif left==0 and abv!=0: # 위쪽에 배추가 있다면
                    field[y][x]=r[abv] # 위엣놈의 테이블에 맞추고  
                    Area[abv]+=1 # 위엣놈이 포함된 영역의 개수 증가

                elif left!=0 and abv==0:# 왼쪽에 배추가 있다면
                    field[y][x]=r[left] # 왼쪽놈의 테이블에 맞추고 
                    Area[left]+=1 # 왼쪽놈이 포함된 영역의 개수 증가

                elif left!=0 and abv!=0: # 왼쪽과 위쪽 베추가 있다면
                    if r[left]>r[abv]: # 왼쪽배추의 테이블값이 크다면
                        field[y][x]=r[abv] # 위쪽놈의 테이블값에 맞추고 
                        r[left]=r[abv] # 왼쪽놈도 위쪽놈에 맞춰준다
                        Area[r[abv]]+=1 # 위쪽놈이 포함된 영역의 개수 증가

                    else: # 위쪽 배추의 값이 크다면 
                        field[y][x]=r[left]  
                        r[abv]=r[left] 
                        Area[r[left]]+=1 # 왼쪽놈에 맞춰준다
    
    for k in range(1,num+1):
        if k!=r[k]: # 숫자랑 테이블이랑 안 맞으면
            r[k]=r[r[k]] # 사실 걘 r[k]에 붙어있는 녀석임
            Area[r[k]]+=Area[k] # r[k] 의 영역에 k영역 개수만큼 더해서 재조정
            Area[k]=0 # 군더더기 삭제
    
    # 안해도 되는 부분
    # for y in range(n):
    #     for x in range(m):
    #         if field[y][x]>0: # 배추가 있으면
    #             field[y][x]=r[field[y][x]] # 테이블의 값으로 배추 색칠

    cnt=0
    for num in Area: # 0이 아닌 원소==독립된 배추
        if num!=0:
            cnt+=1 # 카운트 증가
    print(cnt) # 출력

nahwasa 2년 전 1

반례라기엔 애매한데, 일단 아래 케이스에 대해 동작하지 않습니다.

1
1 1 1
0 0

kjkj5868 2년 전 0

감사합니다! 해당 케이스에 대해서 배열크기문제가 있었네요! 이 부분은 수정했습니다. 그런데 여전히 25%에서 틀렸습니다가 나오네요ㅠㅠ

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

문제

문제

출처

ICPC

25%에서 틀렸습니다 나오는데 반례 부탁드려도 될까요?

kjkj5868 2년 전 0

nahwasa 2년 전 1

kjkj5868 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말