[백준_파이썬]4963번_섬의 개수

내 풀이1 - dfs

- 여기서는 dy = dx[::-1] 작동X(그럴 수 밖에 ,, ㅎㅎ)

import sys
sys.setrecursionlimit(100000) # 재귀를 이용한 dfs로 풀었기 때문에 제한 설정 필요
# 대각선으로도 이동가능하므로 8가지 경우의 수
dx = [1, -1, 0, 0, 1, 1, -1, -1]
dy = [0, 0, 1, -1, 1, -1, 1, -1 ]

def dfs(x, y):
        # 방문처리
        maps[x][y] = 2

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

            # 범위를 넘어가지 않으면서 
            if 0 <= nx < h and 0 <= ny < w:
                # 움직이고자 하는 곳이 땅이라면
                if maps[nx][ny] == 1:
                    # 더 깊게 가주기
                    dfs(nx, ny)

while True:
    w, h = map(int, input().split())

    # 종료조건
    if w == 0 and h == 0:
        break

    # 정보받기
    maps = []
    for _ in range(h):
        maps.append(list(map(int, input().split())))
    
    island = 0
    for i in range(h):
        for j in range(w):
            # 땅이라면
            if maps[i][j] == 1:
                dfs(i, j)
                island += 1
    print(island)

 

내 풀이2 - bfs

from collections import deque

dx = [1, -1, 0, 0, 1, 1, -1, -1]
dy = [0, 0, 1, -1, 1, -1, 1, -1]


def bfs(x, y):
    q = deque()
    q.append((x, y))
    # maps[x][y] = 0
    while q:
        x, y = q.popleft()

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

            if nx >= 0 and nx < h and ny >= 0 and ny < w:
                if maps[nx][ny] == 1:
                    maps[nx][ny] = 0
                    q.append((nx, ny))


while True:
    w, h = map(int, input().split())
    # 종료조건
    if w == 0 and h == 0:
        break

    # maps정보 받기
    maps = []
    cnt = 0
    for i in range(h):
        maps.append(list(map(int, input().split())))

    for i in range(h):
        for j in range(w):
            if maps[i][j] == 1:
                cnt += 1
                bfs(i, j)
    print(cnt)