[백준][Python] 1926 그림

그래프, bfs / 실버 1

🎨

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

1926번: 그림

 

내 풀이

from collections import deque

def bfs(x, y):
    global total_painting
    current_area = 0

    visited[x][y] = True
    q = deque()

    if arr[x][y] == 1:
        q.append((x,y))
        total_painting += 1
        current_area = 1

    while q:
        cx, cy = q.popleft()

        for k in range(4):
            nx = cx + dx[k]
            ny = cy + dy[k]

            if nx < 0 or nx >= n or ny < 0 or ny >= m or visited[nx][ny]:  # 범위를 벗어님
                continue
            visited[nx][ny] = True
            if arr[nx][ny] == 1:
                q.append((nx, ny))
                current_area += 1

    return current_area

n, m = map(int, input().split())
arr = [[] * m for _ in range(n)]
visited = [[False] * m for _ in range(n)]
total_painting = 0
broadest_painting = 0

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

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

for i in range(n):
    for j in range(m):
        if not visited[i][j]: # 방문하지 않은 곳
            broadest_painting = max(broadest_painting, bfs(i, j))

print(total_painting)
print(broadest_painting)

bfs(너비 우선 탐색)으로 풀었다.

 

 

코드 설명

 

가로나 세로로 연결된 것을 하나의 그림으로 취급한다. 상하좌우로 이동할 좌표를 리스트에 저장!

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

 

배열 전체를 돌면서, 방문하지 않은 곳이 있다면 bfs를 호출한다. 이때 현재 인덱스를 매개변수로 전달한다.

· broadest_painting: 가장 넓은 그림의 넓이를 저장할 변수

for i in range(n):
    for j in range(m):
        if not visited[i][j]: # 방문하지 않은 곳
            broadest_painting = max(broadest_painting, bfs(i, j))

 

 

✔️ dfs 함수

 

그림을 발견했다면 deque에 인덱스 저장 후, total_painting과 current_area를 1 증가시킨다.

· total_painting: 총 발견된 그림의 개수

· current_area: 현재 그림의 넓이

if arr[x][y] == 1:
        q.append((x,y))
        total_painting += 1
        current_area = 1

 

현재 인덱스에서 상하좌우로 이동한 새 인덱스를 nx, ny에 저장한다.

만약 범위를 벗어난 인덱스이거나 이미 방문한 곳이라면 pass ~ (continue)

그렇지 않다면 방문 처리 해주고,

새 인덱스의 값이 그림이라면(1이라면), deque에 새 인덱스를 추가해 준 뒤 현재 그림의 넓이를 1 증가시킨다.

for k in range(4):
            nx = cx + dx[k]
            ny = cy + dy[k]

            if nx < 0 or nx >= n or ny < 0 or ny >= m or visited[nx][ny]:  # 범위를 벗어님
                continue
            visited[nx][ny] = True
            if arr[nx][ny] == 1:
                q.append((nx, ny))
                current_area += 1

 

현재 그림의 크기를 반환한다. (그림이 없는 경우에는 0을 반환함)

return current_area