[백준] 4963번 : 섬의 개수 with python3

13 Oct 2018

Reading time ~1 minute

문제: https://www.acmicpc.net/problem/4963

dfs

import sys
read = lambda : sys.stdin.readline().strip()
sys.setrecursionlimit(100000)
dx = [0, 0, -1, 1, -1, -1, 1, 1]
dy = [1, -1, 0, 0, 1, -1, -1, 1]

def dfs(matrix, x, y, w, h):
    matrix[x][y] = 0
    for k in range(8):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= nx and nx < h and 0 <= ny and ny < w:
            if matrix[nx][ny] == 1:
                dfs(matrix, nx, ny, w, h)
while True:
    w, h = map(int, read().split())
    if w == h == 0 : break
    matrix = []
    for _ in range(h):
        matrix.append(list(map(int, read().split())))
    cnt = 0
    for i in range(h):
        for j in range(w):
            if matrix[i][j] == 1:
                dfs(matrix, i, j, w, h)
                cnt += 1
    print(cnt)

bfs

import sys
read = lambda : sys.stdin.readline().strip()
sys.setrecursionlimit(100000)
dx = [0, 0, -1, 1, -1, -1, 1, 1]
dy = [1, -1, 0, 0, 1, -1, -1, 1]

def bfs(group, matrix, w, h, x, y, cnt):
    q = [[x, y]]
    group[x][y] = cnt
    while len(q) != 0:
        x, y = q.pop()
        for k in range(8):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx and nx < h and 0 <= ny and ny < w:
                if matrix[nx][ny] == 1 and group[nx][ny] == 0:
                    q.append([nx, ny])
                    group[nx][ny] = cnt

while True:
    w, h = map(int, read().split())
    if w == h == 0 : break
    matrix = [list(map(int, read().split())) for _ in range(h)]
    group = [[0]*w for _ in range(h)]

    cnt = 0
    for i in range(h):
        for j in range(w):
            if matrix[i][j] == 1 and group[i][j] == 0:
                cnt += 1
                bfs(group, matrix, w, h, i, j, cnt)

    # print(group)
    print(cnt)

algorithm 백준