[백준] 섬의 개수 (4963번)

난이도 : Silver2
Link : https://www.acmicpc.net/problem/4963
Tag : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
풀이일자 : 2024년 9월 10일

📌 문제 탐색하기

정사각형으로 이루어져 있는 섬과 바다 지도가 주어졌을 때 섬의 개수를 세는 문제이다.

섬의 조건
상하좌우대각선 방향으로 이어져 있다면 하나의 섬으로 간주한다.

따라서 이 문제는 BFS를 이용하여 육지가 발견되었을 경우 이동할 수 있는 8가지 방향에 대해서 탐색한 뒤 탐색한 곳의 육지를 바다로 바꿔준다면 최소한의 탐색으로 섬의 개수를 구할 수 있을것이다.

가능한 시간복잡도

모든 곳이 육지일 확률이 있기 때문에 가능한 시간복잡도의 가장 최악인 경우는 지도의 넓이와 같다. W, H의 범위는 50보다 작거나 같은 양의 정수 이므로 시간복잡도상 BFS로 접근했을 때 문제는 없어보인다.

📌 문제 접근 방법

1. 전체 지도에서 for문을 이용하여 육지를 찾는다.
2. 육지를 찾았다면 육지로부터 이어져있는 육지를 찾기위해 BFS를 이용하여 8방향으로 탐색한다.
3. 탐색한 곳은 바다로 바꿔 재탐색을 방지한다.
4. BFS를 호출 할때 육지 카운트를 하나 올려 육지의 개수를 센다.

📌 코드 설계하기

1. 8방향으로 이동할 수 있는 방향을 설정한다.

   #8방향
   dx = [1,1,1,0,0,-1,-1,-1]
   dy = [1,0,-1,1,-1,1,0,-1]

2. BFS 함수를 작성한다.

   • queue에 처음 좌표를 넣어준다.
   • 처음 좌표의 육지를 바다로 바꿔 재탐색을 방지한다.
   • queue에 원소가 존재할때 동안 x,y를 업데이트 해준다.
   • 8방향으로 이동했을때 이동할 수 있는 지 파악하고 육지일 경우 같은 육지로 설정하기 위해 바다로 바꾼다.

3. W,H를 입력받는다.

4. W,H가 0, 0 이 들어올때까지 테스트케이스를 반복한다.

5. W,H를 통해 지도를 grid에 저장한다.

6. grid에서 육지를 찾았을 경우 BFS 함수를 실행하고 육지 카운트를 올린다.

📌 시도 회차 수정 사항

📌 정답 코드

from collections import deque
import sys
#8방향
dx = [1,1,1,0,0,-1,-1,-1]
dy = [1,0,-1,1,-1,1,0,-1]

def BFS(x, y):
    queue = deque()
    queue.append([x,y])
    grid[y][x] = 0
    while queue:
        x,y = queue.popleft()
        for i in range(8):
            if (x + dx[i]) >= 0 and (x + dx[i]) < w and (y + dy[i]) >= 0 and (y + dy[i]) < h:
                if grid[y+dy[i]][x+dx[i]] == 1:
                    queue.append([x+dx[i],y+dy[i]])
                    grid[y+dy[i]][x+dx[i]] = 0

while True: # 0 0이 들어올때까지 무한 반복
    w,h = map(int,input().split())
    if w == 0 and h == 0:
        break
    grid = list()
    answer = 0
    for i in range(h):
        grid.append(list(map(int,sys.stdin.readline().split()))) #지도 만들기

    for i in range(h): #y
        for j in range(w): # x
            if grid[i][j] == 1: # [y][x]
                answer += 1
                BFS(j,i)
    print(answer) #섬의 개수 출력