글 읽기 - 파이썬 배추지렁이... 반례를 부탁드립니다.

gyjinro 3년 전 0

케이스 마다 맵 만들고 배추를 잘 밟고 다녔다고 생각했는데.. 틀렸다고 나오내요..

실패는 시간초과라고 생각핬는데 ㅠ 무언가 빼 먹은게 있는 듯 합니다.

고수님들 반례나 틀린 부분 말씀 좀 부탁드립니다. ㅠ

import sys
from collections import deque
# 4 방향
di = {0: (0, 1),
      1: (1, 0),
      2: (0, -1),
      3: (-1, 0)}

# 노드(p위치, d방향)
class node:
    def __init__(self, p, d=0):
        self.p = p
        self.d = d

def main(M, N, K):
    # 배추밭 초기화
    c_field = []
    for _ in range(N):
        c_field.append([0] * M)
    # 스택, 큐, 지렁이 수 초기화
    stack = []
    que = deque()
    count = 0
    # 밭에 배추 배치하고 큐에 노드 넣기
    for _ in range(K):
        cabage = list(map(int, sys.stdin.readline().split()))
        c_field[cabage[1]][cabage[0]] = 1
        que.append(node((cabage[1],cabage[0])))
    # 스택과 큐가 빌 때까지 탐색
    while stack or que:
        loc = que.popleft()
        if c_field[loc.p[0]][loc.p[1]] == 1:
            count += 1
            stack.append(loc)
        while stack:
            c_node = stack.pop()
            p = c_node.p
            d = c_node.d
            while d < len(di):
                c_field[p[0]][p[1]] = 2
                temp_p = (p[0] + di[d][0], p[1] + di[d][1])
                if 0<= temp_p[0] < N and 0<= temp_p[1] < M and \
                        c_field[temp_p[0]][temp_p[1]] == 1:
                    stack.append(node(p, d + 1))
                    p = temp_p
                else:
                    d += 1
    return count

T = int(sys.stdin.readline())
for _ in range(T):
    M, N, K = map(int, sys.stdin.readline().split())
    print(main(M, N, K))

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

문제

문제

출처

ICPC

파이썬 배추지렁이... 반례를 부탁드립니다.

gyjinro 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말