글 읽기 - 왜 틀렸는지 이해가 잘 가지 않습니다...

hjames2000 1년 전 0

아래의 소스코드에 대해, 이 문제의 어떤 반례가 문제가 되는 것인지 잘 이해가 가지 않아서 질문 올립니다.

자체적으로 생각해본 예시들에서는 틀린 게 발견이 되지 않았는데, 알려주시면 감사하겠습니다 ㅠㅠ

import sys
input=sys.stdin.readline

sys.setrecursionlimit(2600)

def makecluster(where): #
    global loc
    global m
    global n
    loc.remove(where)#양옆, 위아래에 대해 검사할 때 이 점이 다시 검색되면 안 되므로 미리 제거
    for i in range(-1,2,2):#가로방향으로 +-1
        if where[0]+i<0:
            continue
        if where[0]+i>=m:
            continue
        if [where[0]+i,where[1]] in loc:
            makecluster([where[0]+i,where[1]])#양옆 중에 배추가 있는 칸이 있으면 그 점에 대해 함수를 재귀적으로 실행
    for i in range(-1,2,2): #세로방향으로 +-1
        if where[1]+i<0:
            continue
        if where[1]+i>=m:
            continue
        if [where[0],where[1]+i] in loc:
            makecluster([where[0],where[1]+i])

tempstr=' '

T=int(input())

for a in range(T):
    m, n, k=map(int, input().split())
    
    loc=[[0,0] for _ in range(k)]
    clusteridx=0
    
    for i in range(k):#입력
        tempstr=input()
        loc[i]=list(tempstr.split())
        for j in range(2):
            loc[i][j]=int(loc[i][j])
            
    while loc: #loc이 완전히 비어서 더 이상 검색할 대상이 없을 때까지              
        for list1 in loc:
            makecluster(list1) 
            clusteridx+=1#재귀적 탐색이 종료되면 클러스터 수를 세는 변수에 1 더하기
    
    print(clusteridx)

dong5995 1년 전 1

이 글에 있는 반례에서 오답이 나오네요

글 읽기 - 파이썬 반례 좀 부탁드립니다. (acmicpc.net)

hjames2000 1년 전 0

원인 찾았습니다.

중간에 n을 써야되는데 m을 쓴 오타 하나가 문제였네요..ㅋㅋ

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

문제

문제

출처

ICPC

왜 틀렸는지 이해가 잘 가지 않습니다...

hjames2000 1년 전 0

dong5995 1년 전 1

hjames2000 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말