[백준] 플러드필

2667번. 단지번호 붙이기

dx, dy 는 행열의 의미이다. dfs,bfs 의 기본을 잘 알면 쉽게 풀 수 있는 문제.

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

bfs

def solution(x,y):
    global arr,check,dx,dy
    q = []
    q.append((x,y))
    check[x][y] = True
    count = 1
    while q:
        x,y = q.pop(0)
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0 <= nx < len(arr) and 0 <= ny < len(arr):
                if arr[nx][ny] == 1 and check[nx][ny] == False:
                    q.append((nx,ny))
                    check[nx][ny] = True
                    count += 1
    return count


N = int(input())
arr = [list(map(int,list(input()))) for _ in range(N)]
check = [[False] * N for _ in range(N)]
dx = [0,0,1,-1]
dy = [1,-1,0,0]
answer = 0
c_list = []
for i in range(N):
    for j in range(N):
        if arr[i][j] == 1 and check[i][j] == False:
            c_list.append(solution(i,j))
            answer += 1
print(answer)
c_list.sort()
for i in range(len(c_list)):
    print(c_list[i])

dfs

def dfs(x, y):
    global arr, check, dx, dy, c_count
    check[x][y] = True
    c_count += 1
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if 0 <= nx < len(arr) and 0 <= ny < len(arr):
            if check[nx][ny] == False and arr[nx][ny] == 1:
                dfs(nx, ny)


N = int(input())
arr = [list(map(int,list(input()))) for _ in range(N)]
check = [[False] * N for _ in range(N)]
dx = [0,0,1,-1]
dy = [1,-1,0,0]
answer = 0
c_list = []
c_count = 0
for i in range(N):
    for j in range(N):
        if arr[i][j] == 1 and check[i][j] == False:
            dfs(i,j)
            answer += 1
            c_list.append(c_count)
            c_count = 0
print(answer)
c_list.sort()
for i in range(len(c_list)):
    print(c_list[i])

4963번. 섬의 개수

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

def solution(x,y):
    global dx,dy,arr,check
    q = []
    check[x][y] = True
    q.append((x,y))

    while q:
        i,j = q.pop(0)
        for idx in range(8):
            nx,ny = i+dx[idx],j+dy[idx]
            if 0<= nx < len(arr) and 0<= ny < len(arr[0]):
                if check[nx][ny] == False and arr[nx][ny] == 1:
                    q.append((nx,ny))
                    check[nx][ny] = True


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

while True:
    w, h = map(int,input().split())
    if w == 0 and h == 0:
        break
    arr = [list(map(int,input().split())) for _ in range(h)]
    check = [[False] * w for _ in range(h)]
    answer = 0
    for x in range(h):
        for y in range(w):
            if arr[x][y] == 1 and not check[x][y]:
                solution(x,y)
                answer += 1
    print(answer)