[백준] 4963 파이썬 풀이

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

4963번: 섬의 개수

 

dfs/bfs로 풀 수 있는 문제인데 특이점은 대각선 방향도 고려해주어야 하는 것이다. 

상하좌우 + 대각선 방향 = 총 8가지의 경로를 확인하면 된다. 

1) dfs 풀이 

 

import sys
sys.setrecursionlimit(10000)


def dfs(x, y):
    dx = [-1, 1, 0, 0, -1, -1, 1, 1]
    dy = [0, 0, -1, 1, -1, 1, -1, 1]  # 8개 방향
    a[x][y] = 0

    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        if (0 <= nx < h) and (0 <= ny < w) and a[nx][ny] == 1:
            dfs(nx, ny)

while True:
    w, h = map(int, input().split())
    if w == 0 or h == 0:
        break
    a = []
    for i in range(h):
        a.append(list(map(int, input().split())))
    result = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] == 1:
                dfs(i, j)
                result += 1
    print(result)

 

2) bfs 풀이

 

from collections import deque

dx = [-1, 1, 0, 0, -1, -1, 1, 1]
dy = [0, 0, -1, 1, -1, 1, -1, 1]  # 8개 방향

def bfs(x, y):
    a[x][y] = 0
    q = deque()
    q.append([x, y])
    while q:
        x, y = q.popleft()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and a[nx][ny] == 1:
                a[nx][ny] = 0
                q.append([nx, ny])



while True:
    w, h = map(int, input().split())
    if w == 0 or h == 0:
        break
    a = []
    for i in range(h):
        a.append(list(map(int, input().split())))
    result = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] == 1:
                bfs(i, j)
                result += 1
    print(result)

 

아래건은 dfs, 위의 풀이는 bfs로 풀었을 때 각각의 결과이다