[백준] 1926 그림 (파이썬/python)

🎈문제

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

 

🎁어떤 알고리즘?

1. 그래프 탐색 속도 자체는 bfs가 빠르다.

2. 그래프가 크거나 경로의 특징을 저장해야 할 경우는 dfs가 유리하다.

3. 그래프가 크지 않고 최단 거리를 구해야 하는 경우는 bfs가 유리하다.

4. 이 문제의 경우 그래프가 크지 않으므로 bfs를 사용하기로 결정.

 

💻코드

from collections import deque

# 그림 넓이를 반환하는 bfs함수
def bfs(x,y):
    deq = deque()   # 큐 설정
    deq.append([x,y])   # 현재 좌표 큐에 삽입
    count_area = 1  # 현재 좌표 방문 후 큐에 삽입했으므로 1부터
    graph[x][y] = 0 # 현재 좌표 방문 처리
    # 상하좌우 좌표
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]
    while deq:
        x,y = deq.popleft() # 큐에서 원소를 빼내며 탐색 시작
        for i in range(4):  # 빼낸 원소 상하좌우 탐색
            nx = x + dx[i]
            ny = y + dy[i]
            # 도화지 벗어난 경우 무시
            if nx < 0 or nx > (n-1) or ny < 0 or ny > (m-1):
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                count_area += 1 # 그림 넓이 +1
                deq.append([nx,ny]) # 좌표 큐에 저장

    return count_area

# n: 세로(x), m: 가로(y)
n,m = map(int,input().split())
# 도화지
graph = []
for i in range(n):
    graph.append(list(map(int,input().split())))
# 그림 크기 저장할 리스트
area_lst = []

# 탐색 시작
for i in range(n):
    for j in range(m):
        if graph[i][j]: # 해당 칸의 값이 1이면
            area_lst.append(bfs(i,j))   # bfs 탐색으로 알아낸 그림 넓이 area_lst에 삽입

cnt = len(area_lst) # 그림 개수
print(cnt)
if cnt == 0:
    print(0)
else:
    print(max(area_lst))

 

🎄코드 설명

그림의 개수와 가장 넓은 그림의 넓이를 출력하는 문제이다.

1. 도화지 크기 n,m을 입력받고, n과 m이 세로에 해당하는지, 가로에 해당하는지를 꼭 적어놓아 나중에 코드를 작성하면서 헷갈리는 일이 없도록 한다.

2. 도화지를 2차원 배열로 입력받을 수 있도록 한다.

3. 모든 그림의 넓이를 알아야 가장 넓은 그림의 넓이를 알 수 있으므로 그림 크기를 저장할 리스트를 만들어준다.

4. 앞서 bfs를 사용하기로 결정했다. bfs는 모든 칸을 확인하는 기법(시간복잡도는 O(N)) 이므로 이중 for문을 통해 모든 칸을 한번씩 접근할 수 있도록 한다.

5. 접근한 해당 칸의 값이 0이면 그림이 아니므로 무시하고, 값이 1이면 해당 칸부터 그림의 넓이를 조사해서 리스트에 추가하도록 한다.

6. 여기까지 코드를 작성 후, 그림의 넓이를 조사해서 리스트에 추가하도록 하기위해 그림의 넓이를 반환하는 함수인 bfs()를 작성한다.

7. bfs는 큐를사용하는 기법이므로 큐를 하나 만들어주고, 해당 칸은 이미 값이 1임을 확인하고 bfs함수로 들어왔으므로 넓이를 파악하기 위해 설정한 변수 count_area = 1로 설정한다. 또한 해당 칸의 값을 0으로 설정함으로써 방문처리를 한다.

8. 주변 상하좌우 4방향을 살피기 위해 dx와 dy를 설정한다.

9. 큐가 모두 비게 되면 while문을 탈출할 수 있도록 한다.

10. 큐에서 원소를 빼내며 해당 좌표부터 탐색 시작.

11. 빼낸 원소(좌표)의 상하좌우를 탐색하기 시작한다.

12. 해당 도화지를 벗어난 좌표는 무시되도록 한다.

13. 해당 좌표로부터 상하좌우를 탐색하는데, 탐색된 좌표의 값이 1이면 해당 칸의 값을 0으로 설정하고, count_area에 +1 한뒤, 큐에 집어 넣어서 서 그 좌표 또한 상하좌우를 탐색할 수 있도록 한다.

14. 큐가 비어서 해당 좌표로부터 인접한 모든 칸을 조사한 후, 그 넓이를 반환한다.

15. 반환받은 넓이를 area_lst에 해당칸과 이어져있는 모든칸의 넓이(즉, 그림의 넓이)를 추가한다.

16. area_lst에 모든 그림의 넓이가 들어가 있으므로, 길이를 조사하면 그림의 개수를 알 수 있다.

17. 출력