[Python] 백준 13746: Islands

 solved.ac 기준 Silver 1

 

문제

You are mapping a faraway planet using a satellite. The planet's surface can be modeled as a grid. The satellite has captured an image of the surface. Each grid square is either land (denoted as 'L'), water (denoted as 'W'), or covered by clouds (denoted as 'C'). Clouds mean that the surface could either be land or water; you cannot tell.

An island is a region of land where every grid cell in the island is connected to every other by some path, and every leg of the path only goes up, down, left or right.

Given an image, determine the minimum number of islands that is consistent with the given image.

번역

 먼 행성을 위성으로 관측하고 있습니다. 행성의 표면은 그리드 형태로 모델링할 수 있습니다. 위성이 표면의 이미지를 캡처했습니다. 각 그리드 사각형은 땅('L'), 물('W'), 또는 구름('C')으로 덮여 있습니다. 구름은 표면이 땅일 수도 있고 물일 수도 있다는 것을 의미하며, 구름 때문에 알 수 없습니다.

 섬은 그리드 셀 중 땅으로 이루어진 영역이며, 섬 내의 모든 그리드 셀은 어떤 경로를 통해 서로 연결되어 있습니다. 이 경로의 각 구간은 위, 아래, 왼쪽 또는 오른쪽으로만 이동합니다.

 주어진 이미지를 바탕으로, 가능한 최소 섬의 수를 구하십시오.

입력

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input contains two integers, r and c (1 ≤ r,c ≤ 50), which are the number of rows and the number of columns of the image. The next r lines will each contain exactly c characters, consisting only of ‘L’ (representing Land), ‘W’ (representing Water), and ‘C’ (representing Clouds).

출력

Output a single integer, which is the minimum number of islands possible.

예제 입력 1

4 5
CCCCC
CCCCC
CCCCC
CCCCC

예제 출력 1

0

예제 입력 2

3 2
LW
CC
WL

예제 출력 2

1

 

정답 코드

from collections import deque

r, c = map(int, input().split())
planet = [list(input()) for _ in range(r)]

visited = [[False] * c for _ in range(r)]
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]

count = 0
for i in range(r):
    for j in range(c):
        if planet[i][j] == 'L' and not visited[i][j]:
            count += 1

            q = deque()
            q.append((i, j))
            visited[i][j] = True
            while q:
                x, y = q.popleft()

                for dx, dy in d:
                    new_x, new_y = x + dx, y + dy

                    if 0 <= new_x < r and 0 <= new_y < c:
                        if planet[new_x][new_y] == 'L' or planet[new_x][new_y] == 'C':
                            if not visited[new_x][new_y]:
                                q.append((new_x, new_y))
                                visited[new_x][new_y] = True

print(count)

 

 정답으로 섬이 존재할 수 있는 최소의 개수를 구해야 하므로, 구름으로 가려진 영역이 모두 땅이라고 가정하고 해야한다. 그렇기 때문에 각 그려져 있는 땅을 기준으로 구름이나 다른 땅 부분을 방문하며 하나의 영역을 그려내는 식으로 계산을 한다. BFS를 이용했다.

 사실 문제 자체 보다는 영어 독해하는 데 오래걸렸다.