(Python) 백준 4963

백준 4963

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	53849	27142	19495	49.252%

문제

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

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

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

입력

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

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

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

출력

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

---

답안

from collections import deque
import sys

def get_adjacent(row, col, h, w):
    return filter(
        lambda x: not (x[0] == row and x[1] == col) and (0 <= x[0] < h and 0 <= x[1] < w),
        ((y, x) for y in range(row-1, row+2) for x in range(col-1, col+2))
    )

def bfs(visited, row, col):
    queue = deque([(row, col)])
    visited[row][col] = True
    while queue:
        row, col = queue.popleft()
        for row, col in get_adjacent(row, col, len(visited), len(visited[0])):
            if not visited[row][col]:
                visited[row][col] = True
                queue.append((row, col))
    return 1

while True:
    result = 0
    w, h = map(int, sys.stdin.readline().split())
    if h == 0:
        break

    visited = []
    for _ in range(h):
        visited.append(list(map(lambda x: not int(x), sys.stdin.readline().split())))

    for row in range(h):
        for col in range(w):
            if not visited[row][col]:
                result += bfs(visited, row, col)
    
    print(result)

풀이

인접한 섬의 그룹의 개수를 세는 문제이다.

그래프 탐색을 이용한다면 인접한 섬의 개수를 중복하여 세는 일 없이 답을 도출할 수 있겠다는 생각이 들어, BFS를 이용하여 문제를 풀었다.

while True:
    result = 0
    w, h = map(int, sys.stdin.readline().split())
    if h == 0:
        break

입력을 받는 부분이다. 지도의 너비와 높이에 해당하는 w와 h를 입력받고, 만약 h에 0이 입력되면 테스트 케이스 입력받기를 중단한다.

visited = []
for _ in range(h):
    visited.append(list(map(lambda x: not int(x), sys.stdin.readline().split())))

visited 리스트는 섬에 방문하였는지 (섬을 세었는지) 판단하기 위한, boolean 값으로 이뤄진 리스트이다. 주어진 지도와 가로, 세로 크기가 같게 초기화하였으며, 바다 타일의 경우 방문한 것으로 처리하였다.

for row in range(h):
    for col in range(w):
        if not visited[row][col]:
            result += bfs(visited, row, col)

print(result)

BFS(너비 우선 탐색)을 통해, 만약 방문하지 않은 섬을 방문하게 되면 result에 1을 더함으로써 섬의 개수를 센다.

bfs() 함수 내부에서는, 방문하지 않은 타일(row, col)을 입력하면 그 타일과 인접한 타일들을 모두 방문 처리함으로써 중복으로 타일의 개수를 세는 것을 방지한다.

def bfs(visited, row, col):
    queue = deque([(row, col)])
    visited[row][col] = True
    while queue:
        row, col = queue.popleft()
        for row, col in get_adjacent(row, col, len(visited), len(visited[0])):
            if not visited[row][col]:
                visited[row][col] = True
                queue.append((row, col))
    return 1

BFS를 python으로 구현한 부분이다.

인접한 타일들의 row, column을 계속하여 queue에 넣는 방법을 통해 BFS를 구현한다.

queue 안의 element가 하나도 없다는 것은 인접한 타일 중 방문 가능한 타일이 없다는 것이므로, 함수 실행을 종료하고, 섬 개수를 하나 증가시키기 위해 1을 return한다.

def get_adjacent(row, col, h, w):
    return filter(
        lambda x: not (x[0] == row and x[1] == col) and (0 <= x[0] < h and 0 <= x[1] < w),
        ((y, x) for y in range(row-1, row+2) for x in range(col-1, col+2))
    )

이때, 문제에서 “인접한 타일”이란 해당 타일의 가로, 세로 또는 대각선으로 연결되어 있는 타일이라고 정의하고 있다.

해당 타일의 가로, 세로, 대각선으로 1의 거리만큼 떨어져 있는 모든 타일의 좌표들을 구하되,

• 자기 자신 타일의 좌표와,
• index out of range error를 방지하기 위해, 주어진 지도 밖에 있는 유효하지 않은 좌표는 반환하지 않도록 한다.

만약

5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0

과 같은 테스트 케이스를 이 코드로 실행시키면,

(0, 0), (1, 0), (2, 0), (3, 0),
(0, 2),
(2, 2), (3, 3), (2, 4)

순서로 타일을 방문한 뒤 섬의 개수 3을 출력한다.