백준 Nr 4936 섬의 개수 [Python] 코드

python / Algorithm / KOR

2022.07.14.

1. 문제 설정 확인

백준 문제 링크

주어진 값에 따라 “섬”의 개수를 찾아야 한다.
주어지는것은 W X H 로 이뤄진 2차원 배열이다.
문제 예시에 따르면, 섬을 건너갈 때는 상하좌우 뿐만 아니라 대각선 방향으로도 이동할 수 있다 (8방)
W, H가 케이스마다 주어지며, W, H가 각각 0, 0 일 때 프로그램을 종료한다.

2. 문제 풀이

기본적인 DFS 문제이다. 다만 8방으로 이동이 가능하기에 한 칸에서 총 8개 (For i in range(8))의 방향을 탐색해 주어야만 한다.

또한 0 0이 입력으로 들어올 때 까지 계속해서 입력을 받기에 입력받는 line이 굉장히 많다. 따라서 속도 향상을 위해 sys.stdin.readline을 기본 입력으로 사용하였다.

Visited 배열 또한 항상 W X H 크기에 맞게 생성하고, 방문할때마다 방문처리 하는 것을 잊어선 안 된다.

3. 해답 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


#vertical, horizontal, diagonal
x = [0, 0, 1, -1, 1, 1, -1, -1]
y = [1, -1, 0, 0, 1, -1, 1, -1]


def dfs(i, j) :
    visited[i][j] = 1
    for k in range(8) :
        mx = i + x[k]
        my = j + y[k]
        if 0 <= mx < h and 0 <= my < w :
            if field[mx][my] == 1 and visited[mx][my] == 0 :
                visited[mx][my] = 1
                dfs(mx, my)
    return 1


w, h = map(int, input().split())
while w != 0 and h != 0 :
    field = []
    visited = [[0 for _ in range(w)] for _ in range(h)]
    count = 0
    for i in range(h) :
        field.append(list(map(int, input().split())))
    for i in range(h) :
        for j in range(w) :
            if field[i][j] == 1 and visited[i][j] == 0 :
                count += dfs(i,j)

    print(count)
    w, h = map(int, input().split())

어려운 코드는 아니기때문에 보시면서 이해하시면 좋을 것 같습니다.

Source

Baekjoon, 2022.07.18
Pycharm