글 읽기 - 시간 초과를 해결하고 싶습니다.

snowscale 5년 전 0

정답으로 제공된 Java 코드를 봤는데, 흐름은 대동소이하다고 느꼈거든요.

입출력 과정에 문제가 있거나, 아니면 아예 제가 짠 코드가 너무 비효율적인 걸까요? 힌트를 주시면 감사하겠습니다.

# Q: 4963


import sys
from collections import deque


def search(x, y):
    global matrix
    global w, h

    q = deque()

    q.append((x, y))

    def getnear(x, y):
        return [(x-1, y-1), (x, y-1), (x+1, y-1),
                (x-1, y), (x+1,y), (x-1, y+1), (x, y+1), (x+1, y+1)]

    while len(q):
        tmp_x, tmp_y = q.popleft()
        matrix[tmp_y][tmp_x] = 2

        nearlist = getnear(tmp_x, tmp_y)

        for (a, b) in nearlist:
            if 0 <= a < w and 0 <= b < h:
                if matrix[b][a] == 1:
                    q.append((a, b))


while True:
    w, h = map(int, sys.stdin.readline().rstrip().split())
    if w == h == 0:
        exit()

    matrix = [[] for i in range(h)]

    for i in range(h):
        matrix[i] = list(map(int, sys.stdin.readline().rstrip().split()))

    cnt = 0
    for i in range(h):
        for j in range(w):
            if matrix[i][j] == 1:
                search(j, i)
                cnt += 1


    sys.stdout.write('%d\n' % cnt)

jh05013 5년 전 0

https://acmicpc.net/blog/view/...

snowscale 5년 전 0

bfs 수행할 때 왜 꼭 큐를 넣어주는 과정에서 방문체크를 해야하고, 디큐할 때 해서는 안되는지 이유를 몰랐는데 이번에 알아가네요. 답변 감사합니다.

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

문제

문제

출처

ICPC

시간 초과를 해결하고 싶습니다.

snowscale 5년 전 0

jh05013 5년 전 0

snowscale 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말