글 읽기 - 어떤 반례가 있을까요!?

spdlqjdk1012 2년 전 0

아래 항목 (질문 게시판에있던 반례들) 전부 돌렸을 때 문제가 없는 것 같은데 왜 9%에서 틀렸습니다가 나올까요?

3
12 80
23 73
87 51
300

3
3 7
15 7
5 2
260

3
0 0
1 1
2 2
138

3
10 10
10 10
10 10
100

from collections import deque

N = int(input())
xarray = []
yarray = []

for i in range(N):
    a, b = map(int, input().split(" "))
    xarray.append(a)
    yarray.append(b)
xmax = max(xarray)
ymax = max(yarray)

total = 10*10*N
graph = [[0 for i in range(xmax+10)] for i in range(ymax+10)]
visited = [[-1 for i in range(xmax+10)] for i in range(ymax+10)]

for num in range(N):
    for i in range(yarray[num], yarray[num]+10):
        for j in range(xarray[num], xarray[num]+10):            
            graph[i][j]+=1


# for i in range(len(graph)):
#         for j in range(len(graph[0])):
#             print(graph[i][j], end=" ")
#         print()

cnt = 0
def bfs(x, y):
    global graph
    global visited
    global cnt
    xpos = [1, -1, 0, 0]    
    ypos = [0, 0, 1, -1]    
    
    queue = deque([])
    queue.append([x, y])
    
    while queue:
        a, b = queue.popleft()
        for i in range(4):
            tmpx = a+xpos[i]
            tmpy = b+ypos[i]
            
            if 0<=tmpy<len(graph) and 0<=tmpx<len(graph[0]) and visited[tmpy][tmpx] == -1 and graph[tmpy][tmpx]>1:
                queue.append([tmpx, tmpy])
                visited[tmpy][tmpx] = 1
                cnt += (graph[tmpy][tmpx]-1)
                
for i in range(len(graph)):
        for j in range(len(graph[0])):
            if visited[i][j] == -1 and graph[i][j]>1:
                bfs(i, j)
print(total-cnt)

podojom 2년 전 0

와 저도 9프로에서 틀렸습니다가 나옵니다. .

질문자님께서 올리신 반례도 모두 잘 동작하는데,,

어딜 놓친건질 잘 모르겠네요....

sangyoon9 2년 전 0

반례입니다

Input:

0 0

9 9

Output:

200

Answer:

199

여담으로 굳이 bfs를 돌릴 필요 없이 반복문으로 훨씬 쉽고 간단하게 색칠된 좌표의 개수를 셀 수 있습니다

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

문제

문제

출처

ICPC

어떤 반례가 있을까요!?

spdlqjdk1012 2년 전 0

podojom 2년 전 0

sangyoon9 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말