글 읽기 - 반례 좀 찾아주세요 ㅠㅠㅠ

alsgh5821 3년 전 0

도저히 모르겠어요.. 분명 정답인 것 같은데 반례를 못찾겠어요 ㅠㅠㅠ

# 특정 거리의 도시 찾기
from collections import deque

# 지도의 크기
n = int(input())

graph = []
# 지도내 집의 분포
for i in range(n):
    graph.append(list(map(int,input())))

# 이동할 네가지의 방향 정의 (상, 하, 좌, 우 )
dx = [0, -1, 1, 0, 0]
dy = [0, 0, 0, -1, 1]

# 단지의 수
street = 0

# BFS 구현
def bfs(x,y, count):
    # 큐를 구현을 위해 deque 라이브러리 사용
    queue = deque()
    queue.append((x,y))
    # 큐가 빌 때까지 반복하기
    while queue:
        x,y = queue.popleft()

        # 현재 위치에서 4가지 방향으로의 위치 확인
        for i in range(5):
            nx = x + dx[i]
            ny = y + dy[i]
            #미로 찾기 공간을 벗어난 경우 무시
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            #벽인 경우 무시
            if graph[nx][ny] == 0:
                continue
            #해당 노드를 처음 방문하는 경우에만 집의 수를 더함
            if graph[nx][ny] == 1:
                count += 1
                graph[nx][ny] = 2
                queue.append((nx,ny))

    return count

# 단지별 집의 수
result = []
for i in range(n):
    for j in range(n):
        # 단지별 집의 수
        count = 0
        ans = bfs(i, j, count)
        if ans != 0:
            street += 1
            result.append(ans)

result.sort()

# 결과값 출력
print(street)
for i in result:
    print(i)

dldyddlwl 3년 전 0

반례]

alsgh5821 3년 전 0

감사합니다 !!

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

문제

문제

출처

ICPC

반례 좀 찾아주세요 ㅠㅠㅠ

alsgh5821 3년 전 0

dldyddlwl 3년 전 0

alsgh5821 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말