글 작성자: 망고좋아
반응형

4963, 섬의 개수

📁 문제 출처

 

4963번: 섬의 개수

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도

www.acmicpc.net

 

💡 생각

  • 입력은 while문으로 계속 받기
  • 대신 다른 bfs문제와 달리 대각선으로도 이동이 가능하기 때문에 기존 상하좌우에서 4가지 경로를 더 주었다.
  • dx = [0, 0, 1, -1, 1, -1, 1, -1], dy = [1, -1, 0, 0, 1, -1, -1, 1]

 

🛠 나의 코드

from collections import deque
import sys
input = sys.stdin.readline

dx = [0, 0, 1, -1, 1, -1, 1, -1]
dy = [1, -1, 0, 0, 1, -1, -1, 1]

def bfs(graph, a, b):
    queue = deque()
    graph[a][b] = 0
    queue.append((a, b))

    while queue:
        x, y = queue.popleft()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))


while True:
    w, h = map(int, input().split())
    graph = []
    if w == 0 and h == 0:
        break
    for i in range(h):
        graph.append(list(map(int, input().split())))

    ans = 0
    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1:
                bfs(graph, i, j)
                ans += 1
    print(ans)
반응형