글 읽기 - [python]BFS 로 문제를 풀어보았습니다.

buyminari 2년 전 0

이전 게시판에 있는 반례들은 모두 찾아서 입력해보았습니다.

제가 찾은 반례에서는 왜 제출에서 실패하는지 찾을 수 없었습니다.

6% 에서 실패하는 것을 보면 혹시 알고리즘이 틀린게 아니라 출력이나 입력과정에서 틀린게 아닌가 싶은데

정말 모르겠습니다..

import sys
from collections import deque

read = sys.stdin.readline

N = int(read().strip())
board = []
for _ in range(N):
    board.append(list(read().strip()))

complex = []

for y in range(N):
    for x in range(N):
        # 집이 아니면 큐에 넣고 탐색하지 않는다.
        if board[y][x] != "1":
            continue

        # 현재 위치가 집이면 next node 를 큐에 넣고 탐색한다.
        queue = deque([(y, x)])
        count = 0
        while queue:
            y, x = queue.popleft()
            if not (0 <= y < N and 0 <= x < N):
                continue
            if board[y][x] != "1":
                continue
            count += 1
            board[y][x] = "0"
            next_node_list = [
                (y + 1, x),
                (y - 1, x),
                (y, x + 1),
                (y, x - 1),
            ]
            queue.extend(next_node_list)
        complex.append(count)
print(len(complex))
complex.sort()
for c in complex:
    print(c)

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

문제

문제

출처

ICPC

[python]BFS 로 문제를 풀어보았습니다.

buyminari 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말