글 읽기 - python에서 bfs를 이용하여 풀었는데 반례를 못찾겠습니다

kdw9502 5년 전 0

질문게시판에 있는 반례들은 거의 다 입력해봤는데 반례를 찾지 못하겠습니다...

제가 착각하고 있는부분이 어디일까요

import sys,queue
arr = []
sizes = []
n = int(sys.stdin.readline().rstrip())
to = [(-1,0),(1,0),(0,-1),(0,1)]
visit =[[0 for i in range(n)] for j in range(n)]
dong = 0
for i in range(n):
    arr.append(list(map(int,list(sys.stdin.readline().rstrip()))))

for i in range(n):
    for j in range(n):
        if not visit[i][j] and arr[i][j]:
            size = 1
            q = queue.Queue()
            q.put((i, j))
            visit[i][j]=1
            dong += 1
            while q.qsize():
                i,j = q.get()
                for x, y in to:
                    if n > i+x >= 0 and n > j+y >= 0 and not visit[i+x][j+y] and arr[i+x][j+y]:
                        q.put((i+x, j+y))
                        visit[i+x][j+y] = 1
                        size += 1
            sizes.append(size)
print(dong)
sizes.sort()
for size in sizes:
    print(size)

djm03178 5년 전 1

20~24번째 줄에 쓰이는 i, j가 11, 12번째 줄에 쓰이는 i, j랑 겹치고 값을 덮어써버립니다.

서로 다른 변수명을 사용하면 통과됩니다.

kdw9502 5년 전 0

감사합니다! ㅠㅠ 어찌나 자기 실수는 한번 안보이면 영원히 안보이는지 ㅠㅠ

jh05013 5년 전 1

그리고 collections.deque가 queue.Queue보다 훨씬 빠릅니다. queue 모듈은 알고리즘보다는 스레드 프로그래밍에서 주로 사용하는 모듈입니다.

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

문제

문제

출처

ICPC

python에서 bfs를 이용하여 풀었는데 반례를 못찾겠습니다

kdw9502 5년 전 0

djm03178 5년 전 1

kdw9502 5년 전 0

jh05013 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말