[solved.ac 실버2] 4963_섬의 개수 (파이썬, BFS)

제한 사항

 

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

예제

---

나의 풀이

주어진 그래프에서 인접한 곳을 한 그룹으로 묶을 때는 보통 BFS를 사용한다.

일반적으로는 인접하다는 의미를 [상, 하, 좌, 우]로 정의하나 이 문제에서는 4개의 대각선까지 모두 인접하다고 정의했다.

 

전역 변수

from collections import deque

w, h = int(), int()
arr, visited = list(), list()
count = 0
d = [(-1, 0), (0, -1), (1, 0), (0, 1), (-1, -1), (1, -1), (1, 1), (-1, 1)] # ↑ ← ↓ → ←↑ ←↓ ↓→ →↑

사용자에게 입력 받을 w, h, arr 와 방문을 확인할 visited, 섬의 개수를 저장할 count, 그리고 총 8개의 방향을 d에 저장했다.

 

BFS

def bfs(a, b):
    global w, h, arr, count

    if not arr[a][b] or visited[a][b]: return

    queue = deque([(a, b)])
    count += 1

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

        for i in range(8):
            nx, ny = x + d[i][0], y + d[i][1]
            if nx in range(h) and ny in range(w) and not visited[nx][ny] and arr[nx][ny]:
                visited[nx][ny] = True
                queue.append((nx, ny))

global 키워드를 사용해 전역으로 선언된 변수들을 사용한다.

함수의 매개 변수로는 방문을 시작할 좌표를 입력 받는다. 만약 해당 좌표가 바다(0)이거나 이미 방문했다면 바로 빠져나온다.

그리고 BFS를 수행할 것이기 때문에 큐에 매개 변수의 좌표를 넣고 count를 하나 증가시킨다. 위의 if문을 통과했다면 아직 방문하지 않은 섬이라는 뜻이기 때문이다.

 

for문으로 총 8 방향(상, 하, 좌, 우, 4개의 대각선 방향)을 조사한다.

방문할 수 있고(지도를 벗어나지 않고), 아직 방문하지 않았으며 섬(1)인 경우에만 방문 처리를 하면서 큐에 해당 좌표를 집어 넣는다.

 

수행

def solution():
    global w, h, arr, count, visited

    while True:
        # init
        count = 0

        # user_input
        w, h = map(int, input().split())
        if w == h == 0: break

        visited = [[False] * w for _ in range(h)]
        arr = [list(map(int, input().split())) for _ in range(h)]

        # logic
        for x in range(h):
            for y in range(w):
                bfs(x, y)
        print(count)

반복문을 돌 때마다 새로운 케이스를 수행하므로 count를 0으로 초기화해준다.

사용자에게 w와 h를 입력 받는데 둘 다 0이면 반복문을 종료하면서 solution() 함수가 종료된다.

입력 받은 w와 h 크기만큼의 visited 리스트를 만들고, 지도(arr)도 사용자에게 입력 받는다.

그리고 지도의 크기만큼 순회 하며 방문할 수 있는 경우 방문한다. 방문할 수 있고 아직 방문하지 않은 경우에만 bfs 함수 내에서 count를 증가시키므로 이중 for문을 수행하면 count는 섬의 개수가 된다.

 

전체 코드

from collections import deque

w, h = int(), int()
arr, visited = list(), list()
count = 0
d = [(-1, 0), (0, -1), (1, 0), (0, 1), (-1, -1), (1, -1), (1, 1), (-1, 1)] # ↑ ← ↓ → ←↑ ←↓ ↓→ →↑

def bfs(a, b):
    global w, h, arr, count

    if not arr[a][b] or visited[a][b]: return

    queue = deque([(a, b)])
    count += 1

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

        for i in range(8):
            nx, ny = x + d[i][0], y + d[i][1]
            if nx in range(h) and ny in range(w) and not visited[nx][ny] and arr[nx][ny]:
                visited[nx][ny] = True
                queue.append((nx, ny))

def solution():
    global w, h, arr, count, visited

    while True:
        # init
        count = 0

        # user_input
        w, h = map(int, input().split())
        if w == h == 0: break

        visited = [[False] * w for _ in range(h)]
        arr = [list(map(int, input().split())) for _ in range(h)]

        # logic
        for x in range(h):
            for y in range(w):
                bfs(x, y)
        print(count)

solution()

 

채점 결과