[Python] 백준 4963번 섬의 개수

| 문제 내용

2차원 배열에서 1로 표시된 섬의 개수를 구하는 문제. 상하좌우에 대각선까지 고려해서 섬인지 체크해야한다.

 

| 풀이

테스트 데이터에 맞는 지도(matrix)를 설정하고 값이 1인 지점에서 BFS나 DFS로 주변값이 1이면 같은 섬으로 인식해가면서 지도 내 전체 섬의 개수를 체크

 

1) BFS 풀이

import sys
read = sys.stdin.readline

def bfs(queue):
    # 대각선 방향 고려
    dx = [0, 1, 1, 1, 0, -1, -1, -1]
    dy = [1, 1, 0, -1, -1, -1, 0, 1]

    while queue:
        x, y = queue.pop()
        matrix[x][y] = 0

        for d in range(8):
            nx = x + dx[d]
            ny = y + dy[d]

            if (0 <= nx < h) and (0 <= ny < w):
                if matrix[nx][ny] == 1 and (nx, ny) not in queue:
                    queue.append((nx, ny))

while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0:
        break

    matrix = []
    count = 0

    for _ in range(h):
        matrix.append(list(map(int, read().split())))

    for x in range(h):
        for y in range(w):
            if matrix[x][y] == 1:
                count += 1
                bfs([(x, y)])
    print(count)

2) DFS 풀이

import sys
read = sys.stdin.readline
sys.setrecursionlimit(10000) # 안쓰면 런타임에러...

def dfs(x, y):
    # 대각선 방향 고려
    dx = [0, 1, 1, 1, 0, -1, -1, -1]
    dy = [1, 1, 0, -1, -1, -1, 0, 1]

    matrix[x][y] = 0

    for d in range(8):
        nx = x + dx[d]
        ny = y + dy[d]

        if (0<= nx < h) and (0<= ny < w) and matrix[nx][ny] == 1:
            dfs(nx, ny)

while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0:
        break

    matrix = []
    count = 0

    for _ in range(h):
        matrix.append(list(map(int, read().split())))

    for x in range(h):
        for y in range(w):
            if matrix[x][y] == 1:
                count += 1
                dfs(x, y)
    print(count)

 

| 느낀점

확실히 BFS보다 DFS로 풀었을 때 속도가 살짝 더(80ms) 빠르다.

그리고 파이썬 공부를 좀 더 해야겠다 ㅎㅎ;

- input보다는 sys.stdin.readline이 더 빠르다

- 파이썬 변수 참조는 LEGB순으로 이루어진다.

이미지 출처: https://wikidocs.net/80519