[파이썬/Python] 백준 4963번: 섬의 개수

숨·2024년 9월 10일

코테

알고리즘 문제 풀이

목록 보기

70/105

📌 문제 : 백준 4963번

섬과 바다로 이루어진 지도에서 섬의 개수를 세는 문제이다.
입력에 0, 0이 들어올 때까지 반복해서 여러 개의 테스트케이스를 해결해야 한다.

📌 문제 탐색하기

w, h : 지도의 너비와 높이 $(1 ≤ w, h ≤ 50)$

문제 풀이

⭐️ 섬 판단 기준

상하좌우 + 대각선으로 연결되어 있어야 한다.

땅 = 1, 바다 = 0

먼저 입력받은 지도 정보를 2차원 배열로 저장한다.

섬을 찾아야 하므로 전체 지도를 돌면서 땅의 위치를 찾는다.

해당 위치의 땅에서 상하좌우 + 대각선을 확인해 연결된 땅이 있는지 확인한다.
연결된 땅들 = 하나의 섬을 의미하므로 최대한으로 연결된 땅을 찾아야 한다.
→ 이를 BFS로 찾는다!

동일한 곳을 탐색하는 것을 방지해야 한다.
→ 방문 여부를 기록하는 리스트를 추가로 정의한다.

방문하지 않은 지점을 찾아서 해당 지도 밖으로 나가지 않도록 최대로 연결된 땅들을 찾아 개수를 세어준다면 원하는 답을 얻을 수 있다.

🚨 입력에 0, 0이 들어올 때까지 위의 과정을 반복해야 한다는 것을 잊지 말아야 한다!

가능한 시간복잡도

지도 전체 탐색 → $O(w * h)$
8가지 방향 이동 후 BFS 수행 → $O(8 * w * h) = O(w * h)$

최종 시간복잡도
$O(w * h)$ 로 최악의 경우 $O(50^2)$ 이 되어 1초 내 연산 가능하다.

알고리즘 선택

전체 지도를 돌면서 땅의 위치에서 BFS 수행하기

📌 코드 설계하기

BFS 함수 구현
지도 크기 입력
여러 테스트케이스 입력받을 수 있도록 조건 설정
지도 전체 탐색
결과 출력

📌 시도 회차 수정 사항

1회차

    if 0 <= nx < w and 0 <= ny < h and not visited[nx][ny] and graph[nx][ny]:
                                           ~~~~~~~^^^^

예제 입력 1의 3번째 테스트케이스를 실행했는데 위의 코드에서 IndexError: list index out of range가 발생했다.
지도 탐색 시 인덱스 접근을 w, h를 반대로 접근해서 발생한 문제였다. 이중 for문에서 h를 도는 for문 내에 w를 도는 for문을 작성해야하는데 반대로 썼다.

2회차

자꾸 출력이 w * h를 곱한 값이 나왔다.
알고보니 전체 지도 탐색 부분에서 땅인지만 체크하고 방문 여부를 체크하지 않아 이중 for문을 모두 도는 바람에 발생한 일이었다.

📌 정답 코드

import sys
from collections import deque

input = sys.stdin.readline


# BFS 정의
def bfs(x, y):
    queue = deque([(x, y)])
    # 방문 처리
    visited[x][y] = 1

    while queue:
        x, y = queue.popleft()

        # 이동시키기
        for i in range(8):
            nx, ny = x + directions[i][0], y + directions[i][1]

            # 이동 위치가 범위 내이고 방문하지 않았으며 땅이라면 탐색 지속
            if 0 <= nx < h and 0 <= ny < w and not visited[nx][ny] and graph[nx][ny]:
                queue.append((nx, ny))
                visited[nx][ny] = 1


# 8가지 이동 방향 정의
directions = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]

while True:
    # w, h 입력
    w, h = map(int, input().split())

    # 입력에 0, 0 들어올 때까지 반복
    if w == 0 and h == 0:
        break

    else:
        # 지도 정보 입력
        graph = [list(map(int, input().split())) for _ in range(h)]

        # 방문 리스트 만들기
        visited = [[0] * w for _ in range(h)]

        # 섬 개수 초기화
        count = 0

        # 전체 지도 탐색
        for i in range(h):
            for j in range(w):
                # 땅을 찾았다면 BFS 수행
                if graph[i][j] == 1 and not visited[i][j]:
                    bfs(i, j)
                    # 탐색 종료 후 개수 증가
                    count += 1

        # 결과 출력
        print(count)