백준) 4963 - 섬의 개수

이 문제는 외부 포스트의 클론 코딩을 통해 학습을 진행하였습니다. 출처는 글의 마지막 하단부에 기재해 두었습니다.

---

섬의 개수

문제 '섬의 개수'의 링크를 아래에 달아두었습니다.

백준-섬의 개수

풀이

너비 우선 탐색을 활용한 문제입니다.


육지(1)에 해당하는 값을 탐색하면, 그 주변으로 연결되어 있는 육지가 있는 지 탐색, 전부 0으로 만들어 버리는 구조로 섬의 개수를 구합니다.

주변을 탐색하는 건 좌표로써 표시하였고, [0,0] 번을 제외한 전 후 좌 우 대각선 8방향을 탐색하여, 1이 존재할 경우 0으로 바꾸게 됩니다.

1이 존재했던 좌표들을 데크에 집어 넣고(오른쪽으로 들어간다), 왼쪽에서 빼내고, 빼낸 좌표를 위의 과정에 다시 반복 시킵니다.

코드는 다음과 같습니다.

import collections

#너비 우선 탐색 함수
def bfs(v):
    #데크를 생성하고 기준으로 들어온 좌표를 넣어둔다.
    q = collections.deque()
    q.append(v)
    
    #8방향 탐색. 데크에 값이 없을 때 까지 탐색을 진행한다.
    while q:
        v = q.popleft() # 맨 왼쪽 값을 제거한다.
        for a in range(8): # 8방향 탐색을 위해 반복문 사용
            i = v[0] + di[a]# 좌표 계산. di는 8방향의 행 값이 들어가 있다.
            j = v[1] + dj[a]# 좌표 계산. dj는 8방향의 열 값이 들어가 있다.
            if 0 <= i <= h-1 and 0 <= j <= w-1 and ocean[i][j]: # 1-8방향에 속하는 좌표가 유효한 좌표인지, 2-해당 좌표가 육지인지 확인
                ocean[i][j] = 0 # 육지를 0으로 바꿔 다음 탐색 때 걸리지 않게 함
                q.append([i,j]) # 해당 육지 좌표를 데크에 넣어 탐색의 대상이 되게 설정
#8방향 좌표 설정
di = [-1, -1, -1, 0, 0, 1, 1, 1]
dj = [-1, 0, 1, -1, 1, -1, 0, 1]

while True:
    w, h = map(int, input().split()) #지역의 너비와 높이를 받아옴
    if w == 0 and h == 0: # 들어오는 모든 값이 0 0 이면 코드 종료
        break
    ocean = [list(map(int, input().split())) for _ in range(h)] # 높이의 수에 맞게끔 데이터를 받아온다.
    cnt = 0 # 섬의 갯수 변수
    
    #좌표 하나하나를 탐색하면서 육지가 있는지 확인
    for i in range(h):
        for j in range(w):
            if ocean[i][j]: #육지(1)가 있으면 일단 검색한다.
                cnt += 1 #바로 갯수 추가. BFS 함수에서 연결된 육지는 모두 제거 되기에 중복 증가 X
                bfs([i, j]) #해당 좌표를 넣고 주변 탐색
    
    print(cnt)

출처

homebody, 2019년 6월 13일, https://home-body.tistory.com/185