[백준] 4963: 섬의 개수 python 구현 / BFS, 10% 틀렸습니다

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

(한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. )

 

풀이

단지 번호 붙이기와 같은 유형의 문제이다.

그러나 이번 문제는 대각선으로도 이동이 가능하다는 것 ! indexing에 유의하여 대각선 방향을 지시해주면 큰 문제가 없다.

 

추가로, 나는 while문을 통해 height, width의 입력을 받는 것을 조정하였는데, 이렇게 쓰게 되면 0, 0일 때도 코드가 돌아가서 맨 마지막 입력에 종료하는 것이 아니라 cnt=0이 하나가 더 append 된다. 이 부분에서 10% 틀렸습니다가 뜨는 것으로 보아, 10%는 첫 문제부터 틀리는 것,, 본인의 출력 코드를 잘 확인해보자 !

 

CODE

import sys
from collections import deque

q = []
def bfs(st_point):
    # 방향: → ← ↑ ↓ ↗ ↙ ↖ ↘
    dx = [0, 0, -1, 1, -1, 1, -1, 1] 
    dy = [1, -1, 0, 0, 1, -1, -1, 1]

    # queue 정의
    queue = deque()
    queue.append(st_point)
    Map[st_point[0]][st_point[1]] = 0

    while queue:
        now = queue.popleft()
        x, y = now

        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            # map을 벗어나면 pass
            if nx < 0 or ny < 0 or nx > (height-1) or ny > (width-1):
                continue
            # 주변이 섬인 경우
            if Map[nx][ny]:
                queue.append((nx, ny))
                Map[nx][ny] = 0


width, height = 1, 1

result = []
while any([width, height]): # w, h가 True일 때 까지
    ### input
    width, height = map(int, input().split())
    Map = []
    for _ in range(height): # h 만큼 
        Map.append(list(map(int, sys.stdin.readline().split()))) # w 추가

    cnt = 0
    for i in range(height):
        for j in range(width):
            # 섬이 있는 경우만 탐색
            if Map[i][j]:
                cnt += 1
                bfs((i, j))
    if any([width, height]):
        result.append(cnt)

for i in result:
    print(i)