[알고리즘] 백준 1926 그림

문제

그림

접근

1. dfs 문제로 접근을 하려고 했는데 RecurisionError 즉 재귀적 호출할 시에 문제가 있다고 뜬다.

2. bfs로 접근을 해봤다

3. 전체 그림의 개수, 각 그림의 넓이의 최댓값을 구해야한다.

4. 전체 그림의 개수는 num이라는 변수를 지정하고 bfs문을 한바퀴 돌때마다 +1을 해줘서 출력하면 된다.

4. 그림의 넓이는 cnt라는 변수를 두고 특정 조건안에 돌때마다 1씩 더해가는 식으로 하면 된다 ( 이때 넓이는 *가 아닌 +로 생각)

 

풀이

틀린 dfs 풀이

n, m = map(int, input().split())

board = []
for i in range(n):
    board.append(list(map(int, input().split())))

count = []
num = 0


def dfs(x, y):
    global num
    if 0 <= x < n and 0 <= y < m and board[x][y] == 1:
        board[x][y] = 0
        num += 1
        dfs(x+1, y)
        dfs(x-1, y)
        dfs(x, y+1)
        dfs(x, y-1)
        return True
    return False


res = 0
for i in range(n):
    for j in range(m):
        if dfs(i, j) == True:
            res += 1
            count.append(num)
            num = 0

# 그림이 하나도 없는 경우는 0
# if len(count) == 0:
#     count.append(0)

print(res)
print(max(count) if count else 0)

 

정답이 된 bfs풀이

# dfs는 재귀관련 에러가 남 (RecursionError)
from collections import deque
n, m = map(int, input().split())

board = []
for i in range(n):
    board.append(list(map(int, input().split())))

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

visited = [[False]*m for _ in range(n)]

# 전체개수
num = 0


def bfs(x, y):
    global num
    # 각 넓이를 위한 개수
    cnt = 0

    if board[x][y] == 0:
        return -1

    num += 1
    cnt += 1
    visited[x][y] = True

    queue = deque()
    queue.append((x, y))

    while queue:
        x, y = queue.popleft()

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

            if 0 <= nx < n and 0 <= ny < m and board[nx][ny] == 1 and visited[nx][ny] == False:
                visited[nx][ny] = True
                board[nx][ny] = board[x][y] + 1
                cnt += 1
                queue.append((nx, ny))
    return cnt


count = []


for i in range(n):
    for j in range(m):
        if board[i][j] == 1 and visited[i][j] == False:
            count.append(bfs(i, j))
print(num)
# 그림이 하나도 없는 경우는 0
print(max(count) if count else 0)