글 읽기 - 2667번 어디가 잘못됬나요?

zxaq15 4년 전 0

10000

01000

00000

00001

위의 input으로하면 답이 틀리는데 이유를 모르겠습니다

def bfs(start_x, start_y):                  # 이 bfs함수는 matrix의 각 점에서 단지가 형성되어있는지를 가르쳐줌.
    start_point = (start_x, start_y)
    queue = [start_point]
    house_num = 0  # 단지내 집의 수
    while queue:
        x, y = queue.pop(0)
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:  # nx, ny는 이미 dx,dy를 더한값이므로 0과 같아도 인덱스에러가 안남
                if not visited[nx][ny] and matrix[nx][ny]:  # 근데 n까지는 갈필요가없음 그 전 순서에서 n을 이미 탐색하니까
                    visited[nx][ny] = True
                    queue.append((nx, ny))
                    house_num += 1

    return house_num


n = int(input().strip())
matrix = [list(map(int, input())) for _ in range(n)]

dx = [0, 0, -1, 1]  # 상하좌우 탐색을 위해 dx, dy를 설정해놓음.
dy = [-1, 1, 0, 0]

visited = [[False]*n for _ in range(n)]
house_list = []

for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            house_num = bfs(i, j)
            if house_num != 0:    # house_num이 0이면 단지가 없는것이므로 리스트에 추가하지않는다.
                print(f"startPoint: {i, j}")
                house_list.append(house_num)

house_list.sort()

print(len(house_list))
for house_num in house_list:
    print(house_num)

djm03178 4년 전 0

'됬'이 잘못'됐'습니다.

그리고 제목에 문제 번호를 적지 말고 문제 번호를 적는 칸에 문제 번호를 적어주세요.

djm03178 4년 전 1

집이 없는 곳이어도 방문을 안 한 곳이면 일단 bfs를 시작하고 큐에까지 넣기 때문에, 그 주변에만 집이 있으면 계속 탐색을 진행하게 되기 때문에 틀립니다.

이 코드 그대로 실행해봐도 시작점이어서는 안 되는 (0, 1)에서 탐색을 시작하는 걸 볼 수 있고, 그 후 그 주변에 있는 (0, 0)과 (1, 1)이 모두 한 번의 bfs에서 전부 큐에 들어가는 것을 볼 수 있습니다.

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

문제

문제

출처

ICPC

2667번 어디가 잘못됬나요?

zxaq15 4년 전 0

djm03178 4년 전 0

djm03178 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말