[백준(BOJ)] 1926번 : 그림 - PYTHON[파이썬]

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

1926번: 그림

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

---

 

⊙ 문제 접근 과정

 

bfs를 돌려서 그림의 총 개수와 가장 넓은 그림을 찾아내면 된다.

 

bfs를 돌릴 때, 내장 count는 그림의 넓이다. 그 값과 기존에 저장된 큰 그림의 넓이와 비교해서

더 큰 값을 max에 저장해준다.

 

이때 방문을 했는지 안 했는지 알기 위해 visited 리스트를 만들어 체킹해준다.

 

개수는 외부에서 좌표를 넣어줄 때, 방문을 안 했고 1로 표시가 되어있으면 개수 카운트를 올려준다.

 

마지막으로 두 개의 값을 출력해주면 된다.

 

 

 

---

 

⊙ 문제 풀이

 

from collections import deque

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
visited = [[0] * m for _ in range(n)]

q = deque()
maxValue = 0
totalCount = 0


def bfs(x, y):
    q.append((x, y))
    visited[x][y] = 1
    count = 1
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= n or 0 > nx or ny >= m or 0 > ny or visited[nx][ny] or not arr[nx][ny]:
                continue
            q.append((nx, ny))
            visited[nx][ny] = 1
            count += 1
    return count


for i in range(n):
    for j in range(m):
        if arr[i][j] == 1 and not visited[i][j]:
            maxValue = max(maxValue, bfs(i, j))
            totalCount += 1

print(totalCount)
print(maxValue)

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!