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

kyungpyo94 1년 전 0

질문 게시판에 있는 글들 모두 확인해봤는데 틀린답이 안나오네요...

반례 혹은 코드에 잘못된 부분이 있다면 지적 부탁드립니다.

import sys
from collections import deque

input = sys.stdin.readline

for _ in range(int(input())):
    m, n, k = map(int, input().split())

    field = [[0] * n for _ in range(m)]

    for _ in range(k):
        i, j = map(int, input().split())
        field[i][j] = 1
    
    nodes = [[[]] * n for _ in range(m)]
    visited = [[False] * n for _ in range(m)] 
    for i in range(m):
        for j in range(n):
            if field[i][j] == 1:
                # up
                if i > 0 and field[i-1][j] == 1:
                    nodes[i][j].append((i-1, j))
                    nodes[i-1][j].append((i, j))
                # down
                if i < m-1 and field[i+1][j] == 1:
                    nodes[i][j].append((i+1, j))
                    nodes[i+1][j].append((i, j))
                # left
                if j > 0 and field[i][j-1] == 1:
                    nodes[i][j].append((i, j-1))
                    nodes[i][j-1].append((i, j))
                # right
                if j < n-1 and field[i][j+1] == 1:
                    nodes[i][j].append((i, j+1))
                    nodes[i][j+1].append((i, j))
            else:
                visited[i][j] = True
    num = 0
    for i in range(m):
        for j in range(n):
            if not visited[i][j]:
                if field[i][j] == 1:
                    visited[i][j] = True
                    num += 1
                    stack = deque([(i, j)])
                    while stack:
                        cur_i, cur_j = stack.popleft()
                        for node in nodes[cur_i][cur_j]:
                            if not visited[node[0]][node[1]]:
                                visited[node[0]][node[1]] = True
                                stack.append(node)
    print(num)

kravi 1년 전 1

반례 드립니다.

1
3 4 6
1 2
0 0
1 3
0 1
2 1
0 3

ANSWER:
3
WA:
2

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

문제

문제

출처

ICPC

파이썬 반례 좀 부탁드립니다.

kyungpyo94 1년 전 0

kravi 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말