[Python] 백준 알고리즘 4693번: 섬의 개수

이번에 푸는 문제는 백준 알고리즘 4693번: 섬의 개수로 난이도는 Siver 2 에 해당한다.

문제는 다음과 같다.

 

 

사실 이 문제는 2667번 단지번호 붙이기를 풀고 풀어서 수월하게 풀었다.

기존 단지번호 붙이기 문제에서  G[x][y] 기준으로 주변 테두리를 확인하는 것만으로 바꾸면 끝난다.

x,y를 탐색의 기준으로잡고 dx,dy를 만들어서 주변을 탐색하게 만들었다. (다이얼 5를 기준으로 1~9를 탐색한 것과 같은 구조로 만들어놨다)

 

# 작성자 : SH_WON_96
# 2021-01-04
# 알고리즘 - Graph
# 문제번호 : 4963

# 초기 입력값 받기
import sys
from collections import deque
input = sys.stdin.readline
dx, dy = [-1, -1, -1, 0, 0, 1, 1, 1],[-1, 0, 1, -1, 1, -1, 0, 1]

# N 열 M 행
def Calland(N,M):
    # 그래프 생성
    G = [0 for i in range(M)]
    for i in range(M):
        G[i] = list(map(int, input().strip().split(" ")))


    visited = [[0]*N for i in range(M)]

    # print(G)
    # print(visited)

    queue = deque()
    landnum = 0
    for i in range(M):
        for j in range(N):
            if (G[i][j] == 1 and visited[i][j] == 0):
                queue.append((i, j))
                landnum += 1
                visited[i][j] = landnum
                
                #
                while queue:
                    x, y = queue.popleft()
                    for k in range(8):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        if (0 <= nx < M and 0 <= ny < N):
                            if(visited[nx][ny]==0 and G[nx][ny]==1):
                                visited[nx][ny] = landnum
                                queue.append((nx,ny))


    return landnum





#print(Calland(5,4))
while True:
    N, M = list(map(int, input().split(" ")))
    if N == 0 and M == 0:
        break
    else:
        print(Calland(N,M))

 

내일 단지번호 붙이기 문제 다시 리뷰해서 올려야겠다.

---

문제는 아래 ↓링크↓

4963번: 섬의 개수