[Python] 1926번 : 그림

 

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

 

 

문제 3줄 요약

1. 도화지에 그림이 그려진 부분은 1, 그려지지 않은 부분은 0으로 표시되어 있다.

2. 1로 연결된 것은 한 그림이라 정의한다. 대각선 연결은 예외, 가로/세로 연결만 해당

3. 그림의 개수와 가장 큰 그림의 넓이(포함된 1의 개수)를 출력하라.

---

 

BFS와 DFS를 사용한다면

큰 어려움 없이 풀 수 있는 문제라고 느껴졌다.

 

BFS와 DFS의 차이를 잘 모르고 계시다면,

아래 글을 참고하면 좋을 것 같다!

 

https://59travel.tistory.com/76

[Python] 1260번 : DFS와 BFS

 

 

필자는 BFS를 이용하여 문제를 풀었는데

코드를 먼저 함께 봐보자!

 

from collections import deque
def solve(i, j):
    deq, width = deque([[i,j]]), 1
    visited[i][j] = 1

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

        for dx, dy in [(0,1), (1,0), (0, -1), (-1, 0)]:
            nx, ny = x+dx, y+dy

            if 0<=nx<n and 0<=ny<m and not visited[nx][ny] and painting[nx][ny]:
                visited[nx][ny] = 1
                deq.append([nx, ny])
                width += 1

    return width

n, m = map(int, input().split())
painting = [list(map(int, input().split())) for _ in range(n)]
visited = [[0]*m for _ in range(n)]
cnt_picture, max_width = 0, 0

for i in range(n):
    for j in range(m):
        if not visited[i][j] and painting[i][j]:
            cnt_picture += 1
            max_width = max(max_width, solve(i, j))

print(cnt_picture)
print(max_width)

 

 

도화지 중에서 방문하지 않았고 그림이 그려진 부분을

BFS를 활용하여 이어진 그림 탐색을 진행하였다.

 

탐색하기에 앞서

방문하지 않았고 그림이 그려진 부분을 찾았다는 건

그림이 존재한다는 뜻이니

그림의 개수를 +1 해줬다.

 

탐색 과정에서는

상하좌우칸을 돌아보며 그림이 그려진 부분이 있다면,

방문 체크를 해주고 구하고자 하는 넓이를 +1 해주었다.

 

탐색이 끝났다면 그림의 넓이를 반환해주고

큰 넓은 값이 남을 수 있도록 max 함수를 이용하여 max_width 변수를 업데이트 해줬다.

 

---

 

BFS로 풀어봤으니

다음엔 DFS로도 풀어봐야겠다.

 

끝!