[Python] 그림 (백준 1926번 파이썬)

 

문제

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

입력

첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)

출력

첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.

예제 입력 1

6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1

예제 출력 1

4
9

 

 

---

 

 

0(빈칸), 1(그림) 이므로 BFS가 실행되는 횟수 == 그림의 갯수이고,

BFS가 실행됐을 때 값을 저장해서 구한 최댓값이 가장 큰 그림의 크기 입니다.

 

n,m = map(int, input().split())
graph = [list(map(str, input().split())) for _ in range(n)]
visited = [[False]*m for _ in range(n)]
paint = 0
fill = 0
for i in range(n):
    for j in range(m):
        if graph[i][j]=='1' and visited[i][j]==False and bfs(i,j,visited):
            paint += 1

 

문제 조건에 따라서 입력을 받은 뒤, visited 배열을 생성해 방문처리를 진행합니다.

그림의 갯수 paint, 그림의 넓이 최댓값 fill 을 정의합니다.

 

입력받은 2차원 배열을 순회하며, 그림 부분에 대해서 bfs탐색을 시작합니다.

이 때, 탐색하는 점은 아직 방문하지 않은 visited가 False인 점이어야 합니다.

탐색결과 True가 반환되면, 그림의 갯수에 +1 해줍니다.

 

 

from collections import deque
def bfs(x,y,visited):
    global fill
    max_val = 0
    q = deque()
    visited[x][y] = True
    q.append((x,y))

    while q:
        x,y = q.popleft()
        dx = [-1,0,1,0]
        dy = [0,1,0,-1]
        max_val += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<m and visited[nx][ny]==False:
                if graph[nx][ny] == '1':
                    q.append((nx,ny))
                    visited[nx][ny] = True

    fill = max(fill, max_val)
    return True

 

BFS 함수 생성을 위해 deque를 import 합니다.

이후 큐에 x,y 점을 넣고, 해당 점을 visited = True로 바꿔줍니다. (중복 방문을 피하기 위함)

 

큐에서 값을 꺼내 탐색을 시작합니다.

큐에서 꺼낸 값은 모두 조건을 만족하는 점이므로 그림의 넓이에 +1 해줍니다.

 

4방향에 대해 방향 벡터를 정의한 후, 해당 점이 graph 내에 있고 아직 방문하지 않은 점이며 1인 점이라면

큐에 넣어서 다음 탐색을 예정합니다.

이때, 방문처리 또한 True로 진행해 다음 탐색에서 방금 탐색한 점을 피해야 합니다.

 

더 이상 방문할 지점이 없어 while문이 종료되면, 방금 탐색에서 누적된 넓이를 fill 변수에 갱신합니다.(최댓값 갱신)

이후 True를 리턴하며 종료합니다.

 

 

 

전체 코드

#백준 1926 그림

from collections import deque
def bfs(x,y,visited):
    global fill
    max_val = 0
    q = deque()
    visited[x][y] = True
    q.append((x,y))

    while q:
        x,y = q.popleft()
        dx = [-1,0,1,0]
        dy = [0,1,0,-1]
        max_val += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<m and visited[nx][ny]==False:
                if graph[nx][ny] == '1':
                    q.append((nx,ny))
                    visited[nx][ny] = True

    fill = max(fill, max_val)
    return True

n,m = map(int, input().split())
graph = [list(map(str, input().split())) for _ in range(n)]
visited = [[False]*m for _ in range(n)]
paint = 0
fill = 0
for i in range(n):
    for j in range(m):
        if graph[i][j]=='1' and visited[i][j]==False and bfs(i,j,visited):
            paint += 1

print(paint)
print(fill)