[알고리즘] 4963 섬의 개수

게시물을 작성하면서 복습하는 문제를 선정하는 기준은<solved.ac 티어 실버 2 (Silver 2) 이상>입니다.

※ 본 사진과 해당 게시글 내용의 문제 모두 백준 : 온라인 저지[Baekjoon_OnlineJudge]사이트에서 발췌해왔습니다.

❓ 문제

백준 온라인 저지 (Baekjoon Online Judge) : 4963 섬의 개수


❗ 풀이

My Code

메모리 : 32452KB
시간 : 116ms

  • " 가로, 세로, 대각선 연결 " ▶ dxdy로 이동 방향 조작

섬의 형태를 나타낸 입력값을 m으로 만들어 놓고
각 육지가 시작되는 좌표에서 visited로 체크하면서 나중에 중복 체크되지 않게끔 섬의 갯수 세기 ( 함수 bfs 정의 )

import sys
input = sys.stdin.readline
dx =[0,0,1,-1, 1,1,-1,-1]
dy =[1,-1,0,0, 1,-1,1,-1]

from collections import deque

def bfs(w,h) :
    q = deque()
    q.append([h, w])
    visited[h][w] = 1
    while q:
        h, w = q.popleft()
        for i in range(8):
            nw = w + dx[i]
            nh = h + dy[i]
            if 0 <= nw < W and 0 <= nh < H:
                if m[nh][nw] == 1 and visited[nh][nw] == 0:
                    visited[nh][nw] = 1
                    q.append([nh, nw])


while True :
    W, H = map(int, input().split())
    if W==0 and H ==0 :
        break
    m = []
    visited = [[0]*W for _ in range(H)]
    for _ in range(H) :
        m.append(list(map(int, input().split())))

    land=0
    for i in range(H):
        for k in range(W) :
            if m[i][k] == 1 and visited[i][k] == 0 :
                bfs(k,i)
                land+=1
    print(land)

좋은 웹페이지 즐겨찾기